Pythonで歩行によりk回以上カバーされるブロックの数を数えるプログラム

2つのリストwalksとtargetが与えられているとします。初期状態では、1次元の数直線上の位置0に立っています。|walks[i]| は歩いたステップ数を表し、walks[i] が正の値なら右方向へ、負の値なら左方向へ移動したことを意味します。歩行中は常に1ブロック(隣接する整数位置)ずつ移動します。ここで求めたいのは、target回以上踏まれたブロック(区間)の総数です。

たとえば、入力が walks = [3, -7, 2]、target = 2 の場合、出力は 5 になります。下図のように、[0, 1]、[1, 2]、[2, 3]、[-4, -3]、[-3, -2] の5つの区間がちょうど k = 2 回カバーされているためです。

解き方の考え方

この問題は、各区間の始点と終点だけを記録しておき、あとから座標順に走査しながら通過回数を累積していく手法(いもす法・差分と累積和)を使うと、全ステップを1つずつシミュレートするよりもはるかに効率的に解けます。

具体的には、以下の手順に従います。

• pos := 0 とする(現在位置)
• jumps := ハッシュマップを用意する(キーが存在しない場合のデフォルト値は0)
• walks 内の各 dist に対して、次を実行する
  • jumps[pos] に、dist > 0 なら +1、そうでなければ -1 を加算する
  • jumps[pos + dist] に、dist > 0 なら -1、そうでなければ +1 を加算する
  • pos := pos + dist として現在位置を更新する
• lastpos := 0、level := 0、total := 0 で初期化する
• jumps をキーでソートし、各 (pos, val) のペアに対して、次を実行する
  • level >= target であれば、total := total + (pos - lastpos) とする
  • level := level + val とする
  • lastpos := pos とする
• total を返す

Python実装例

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

from collections import defaultdict

def solve(walks, target):
    pos = 0
    jumps = defaultdict(int)
    for dist in walks:
        jumps[pos] += 1 if dist > 0 else -1
        jumps[pos + dist] -= 1 if dist > 0 else -1
        pos += dist
    lastpos = level = total = 0
    for pos, val in sorted(jumps.items()):
        if level >= target:
            total += pos - lastpos
        level += val
        lastpos = pos
    return total

walks = [3, -7, 2]
target = 2
print(solve(walks, target))

入力

[3, -7, 2], 2

出力

5

アルゴリズムのポイント

この手法では、各歩行を「区間への加算」として捉えます。右方向の歩行なら始点に +1、終点に -1 を記録し、左方向の歩行ならその逆を記録します。その後、座標順に走査しながら累積値 level を更新し、level が target 以上になっている間の区間の長さを合計することで、答えが得られます。

計算量はソートが支配的となり O(n log n) です。これは歩いた距離の総和 S に比例する O(S) の単純なシミュレーションよりも、歩行距離が大きいケースで大幅に高速に動作します。