Pythonで力の作用後の文字列の最終状態を求めるアルゴリズム

問題の概要

長さ n の文字列 S を考えてみましょう。この文字列は、隣り合って並んだ n 個の箱を表現しています。位置 i にある文字「R」は、i 番目の箱が右方向へ押されていることを意味し、「L」は左方向へ押されていることを示します。また、「.」（ドット）は空きスペースを表します。

初期配置からスタートし、各時間単位ごとに、右へ押されている箱はその隣の箱を右へ押すことができます。左方向についても同様の動作が起こります。このとき、それ以上の移動が不可能になった状態での、すべての箱の最終的な位置を求めるのが目的です。

入出力の例

たとえば、入力が「R..R...L.」である場合、出力は「RRRRR.LL.」となります。

解法の考え方

この問題は、右方向と左方向それぞれの「力」を数値として累積する、2 回の走査で解くことができます。具体的な手順は以下の通りです。

1. N を文字列の長さとし、サイズ N の配列 movement を 0 で初期化します。変数 m も 0 にしておきます。
2. 左から右への走査： i を 0 から N-1 まで順に処理します。
   • string[i] が「R」なら、m := N（右向きの最大の力を設定）
   • string[i] が「L」なら、m := 0（力をリセット）
   • それ以外なら、m := max(m − 1, 0)（距離に応じて力を減衰）
   • movement[i] += m
3. 右から左への走査： m を 0 に戻し、i を N-1 から 0 まで逆順に処理します。
   • string[i] が「L」なら、m := N
   • string[i] が「R」なら、m := 0
   • それ以外なら、m := max(m − 1, 0)
   • movement[i] -= m
4. 最後に、movement の各要素 m に対して、m が 0 なら「.」、m > 0 なら「R」、m < 0 なら「L」とした文字を連結して返します。

この手法では、正の値は右向きの力が優勢であることを、負の値は左向きの力が優勢であることを表します。両者の力が打ち消し合う位置は 0 となり、その箱は静止したままになります。

実装コード

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

def get_final_pos(string):
    N = len(string)
    movement = [0] * N
    m = 0
    for i in range(0, N):
        if string[i] == 'R':
            m = N
        elif string[i] == 'L':
            m = 0
        else:
            m = max(m - 1, 0)
        movement[i] += m
    m = 0
    for i in range(N - 1, -1, -1):
        if string[i] == 'L':
            m = N
        elif string[i] == 'R':
            m = 0
        else:
            m = max(m - 1, 0)
        movement[i] -= m
    return "".join('.' if m == 0 else 'R' if m > 0 else 'L' for m in movement)

print(get_final_pos('R..R...L.'))

入力

'R..R...L.'

出力

RRRRR.LL.

計算量について

このアルゴリズムは文字列を前後 2 回走査するだけなので、時間計算量は O(n)、必要な追加メモリも O(n) です。毎秒のシミュレーションを繰り返す素朴な方法（O(n × 時間ステップ数)）と比べて、最終状態をはるかに効率的に求められる点が大きなメリットです。