Pythonで解く！円管内のボールが衝突する回数を求めるアルゴリズム

問題の概要

円状の管（円管）の中に n 個のボールが入っているとします。管の長さは100メートルで、最初は各ボールが「スタート地点」と呼ばれる基準点から i メートル離れた位置に配置されています。ここからボールたちは、それぞれ異なる方向へ向かって管の中を周回し始めます。ボールの移動速度は毎秒0.1メートルです。

2つのボールが同じ地点で出会うと衝突が発生し、衝突したボールは互いに進行方向を反転させます。この過程を 10⁹+6 秒という非常に長い時間にわたって続けたとき、ボール同士が衝突する合計回数を求めるのがこの問題です。各ボールのスタート地点からの初期距離が入力として与えられます。

たとえば、入力が input_array = [0, 10] である場合、出力は 400000 になります。

この例ではボールが2つあり、スタート地点からの距離が入力として与えられています。2つのボールが同じ方向に進むのであれば、衝突は一度も発生しません。しかし方向が異なる場合は何度も衝突を繰り返すことになり、結果的にちょうど 400000 回の衝突が起こります。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• 入力リスト input_array をソートします。
• size := input_array の要素数とします。
• lap_count := (10⁵) × 2 とします。
• output := 2 × lap_count × (size ÷ 2 の商) × (size − size ÷ 2 の商) とします。
• stop := 0 とします。
• i を 0 から size−2 まで1ずつ増やしながら以下を繰り返します。
  • stop が 1 でない場合：
    • input_array[i] + 1 が input_array[i+1] と等しければ、output に 2 を加算し、stop := 1 とします。
    • そうでなければ stop := 0 とします。
  • stop が 1 の場合は stop := 0 とします。
• 最後に output を返します。

基本となる計算式では、ボールを半分ずつの2グループに分けたときのペア数（逆向きに進むボールの組み合わせ）に、観測期間中の周回あたりの衝突回数を掛けることで総衝突数を求めています。さらに、隣接する初期位置がちょうど1メートル差のケースで発生する追加の衝突を補正値として加算しています。

実装例

理解を深めるために、次の実装例を見てみましょう。

def solve(input_array):
    input_array.sort()
    size = len(input_array)
    lap_count = (10**5)*2
    output = 2*lap_count*(size//2)*(size - size//2)
    stop = 0
    for i in range(size - 1):
        if stop != 1:
            if input_array[i] + 1 == input_array[i+1]:
                output += 2
                stop = 1
            else:
                stop = 0
        else:
            stop = 0
    return output

print(solve([0, 10]))

入力

[0, 10]

出力

400000