Pythonで解く!ブラックリストの段を避けてボールが高さ0に落ちる経路の数を数える方法

問題の概要

高さ h と数値リスト blacklist が与えられます。ボールは現在 高さ h にあり、これを高さ 0 まで下ろすゲームを考えます。移動のルールは次の通りです。

• 偶数ラウンド(0から開始):ボールを 1 段・2 段・4 段のいずれかで下げられる
• 奇数ラウンド:ボールを 1 段・3 段・4 段のいずれかで下げられる
• 一部の段はブラックリストに登録されており、ボールがそこに到達すると即座に消滅する

このとき、ボールが高さ 0 に到達する移動方法の総数を求めます。答えが大きくなりすぎる場合は、10⁹ + 7 で割った余りを返してください。

例えば、入力が h = 5、blacklist = [2, 1] の場合、出力は 2 になります。これは次の 2 通りの経路が存在するためです。

• ラウンド 0 で 1 段下がり(5 → 4)、次のラウンドで 4 → 0 へ移動する
• ラウンド 0 で 2 段下がり(5 → 3)、次のラウンドで 3 → 0 へ移動する

解き方のアプローチ

この問題は動的計画法(DP)を使うことで効率的に解けます。手順は以下の通りです。

• blacklist をセット(set)に変換し、要素の存在判定を高速化します
• 0 または h がブラックリストに含まれる場合は、ゴールに到達できないため 0 を返します
• サイズ h+1 の DP テーブルを作成し、各インデックスにペア [0, 0] を格納します
• 初期値として dp[0] = [1, 1] を設定します
• 剰余演算用の定数 m = 10^9 + 7 を定義します
• i を 1 から h まで順に処理します
  • 各 x ∈ {1, 2, 3, 4} について、i − x ≥ 0 かつ i − x がブラックリストに含まれない場合
    • x が 3 以外なら dp[i][0] += dp[i−x][1](偶数ラウンドで許可される移動量による遷移)
    • x が 2 以外なら dp[i][1] += dp[i−x][0](奇数ラウンドで許可される移動量による遷移)
  • dp[i][0] と dp[i][1] を m で割った余りに更新します
• 最終的に dp[h][0] を返します

ここで dp[i][0] は「次の移動が偶数ラウンドになる状態」、dp[i][1] は「次の移動が奇数ラウンドになる状態」での経路数を表しています。ラウンドごとに使える移動量が異なるため、2 つの状態を分けて管理するのがポイントです。

実装例(Python)

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

def solve(h, blacklist):
    blacklist = set(blacklist)
    if 0 in blacklist or h in blacklist:
        return 0
    dp = [[0, 0] for i in range(h + 1)]
    dp[0] = [1, 1]
    m = 10 ** 9 + 7
    for i in range(1, h + 1):
        for x in [1, 2, 3, 4]:
            if i - x >= 0 and i - x not in blacklist:
                if x != 3:
                    dp[i][0] += dp[i - x][1]
                if x != 2:
                    dp[i][1] += dp[i - x][0]
            dp[i][0] %= m
            dp[i][1] %= m
    return dp[h][0]

h = 5
blacklist = [2, 1]
print(solve(h, blacklist))

入力

5, [2, 1]

出力

2

このアルゴリズムの計算量は時間・空間ともに O(h) であり、h が大きい場合でも高速に動作します。