Pythonで全てのボールを各位置に集めるための合計移動距離を効率的に求めるアルゴリズム

0と1のみを含むバイナリリストnumsがあるとします。0は空のセル、1はボールが入っているセルを表します。ここで、numsと同じサイズの新しいリストLを作成し、L[i]にはすべてのボールを位置iに集めるために必要な合計移動距離を格納します。インデックスjからインデックスiへボールを移動する際の距離は |j - i| で表されます。

例えば、入力が nums = [1, 1, 0, 1] の場合、出力は [4, 3, 4, 5] になります。これは以下のように計算できます。

• L[0] = |0 - 0| + |1 - 0| + |3 - 0|
• L[1] = |0 - 1| + |1 - 1| + |3 - 1|
• L[2] = |0 - 2| + |1 - 2| + |3 - 2|
• L[3] = |0 - 3| + |1 - 3| + |3 - 3|

つまり、すべてのボールを L[1] の位置に集めるには、インデックス0のボールを距離1で移動させ、インデックス3のボールを距離2で移動させる必要があります。

解決のためのアプローチ

各位置ごとに毎回全ボールとの距離を計算すると計算量がO(n²)になってしまいますが、左右からの累積情報を活用することでO(n)で効率的に解けます。手順は以下の通りです。

• numsが空の場合は、空のリストを返す
• left_count := 0(現在位置より左側にあるボールの数)
• right_count := 0(現在位置より右側にあるボールの数)
• left_sum := 0(左側のボールを移動させる合計距離)
• right_sum := 0(右側のボールを移動させる合計距離)
• result := 空のリスト
• 最初のループで、すべてのボールについてright_countとright_sumを計算する
• 次のループでは、各インデックスに対して left_sum + right_sum をresultに追加する。その後、現在位置にボールがある場合はright_countを1減らしleft_countを1増やし、left_sumとright_sumを更新して次の位置へ進む
• resultを返す

ポイントは、位置を1つ右に移動するたびに「左側のボールはそれぞれ距離+1」「右側のボールはそれぞれ距離-1」となる性質を利用している点です。これにより、毎回距離を再計算する必要がなくなります。

実装例

以下のPythonコードで具体的な実装を確認しましょう。

def solve(nums):
    if not nums:
        return []

    left_count = right_count = 0
    left_sum = right_sum = 0
    result = []

    for index, num in enumerate(nums):
        if num:
            right_count += 1
            right_sum += index

    for index, num in enumerate(nums):
        result.append(left_sum + right_sum)

        if num:
            right_count -= 1
            left_count += 1

        left_sum += left_count
        right_sum -= right_count

    return result

nums = [1, 1, 0, 1]
print(solve(nums))

入力

[1, 1, 0, 1]

出力

[4, 3, 4, 5]

計算量について

このアルゴリズムは、リストを2回走査するだけなので、時間計算量はO(n)、追加で結果を格納するための空間計算量もO(n)となります。ナイーブなO(n²)のアプローチと比べ、大きな入力に対しても高速に動作するのが特徴です。