概要

\(N\) 段の階段を \(1\) 段・\(2\) 段・\(3\) 段のいずれかで上る方法の数を、壊れている段に着地できないという制約のもとで数える動的計画法（DP）の問題です。

考察

重要な気づき

まず、壊れている段がない場合を考えてみましょう。\(0\) 段目から \(i\) 段目に到達する方法の数を \(dp[i]\) とすると、\(i\) 段目に来るには「\(i-1\) 段目から \(1\) 段上る」「\(i-2\) 段目から \(2\) 段上る」「\(i-3\) 段目から \(3\) 段上る」の \(3\) 通りの直前の状態があります。したがって：

\[dp[i] = dp[i-1] + dp[i-2] + dp[i-3]\]

という漸化式が成り立ちます。これはいわゆる「トリボナッチ数列」に似た構造です。

壊れている段の扱い

壊れている段 \(i\) には着地できないので、\(dp[i] = 0\) とすればよいです。壊れている段から出発することもできないため、その段を経由するすべてのルートが自動的に \(0\) になり、後続の段の計算に正しく反映されます。

具体例（\(N = 5\), 壊れている段 \(= \{2\}\)）

答えは \(dp[5] = 5\) です。\(2\) 段目を避けて上る方法が \(5\) 通りあることが確認できます。

素朴なアプローチとの比較

すべての上り方を再帰的に列挙すると、分岐が指数的に増え、\(N\) が大きい場合（最大 \(10^5\)）には到底間に合いません。DPを使えば各段について \(O(1)\) で計算でき、全体で \(O(N)\) となります。

アルゴリズム

1. 壊れている段の番号を集合（set）に格納する（\(O(1)\) で判定可能にするため）。
2. 配列 \(dp[0..N]\) を用意し、\(dp[0] = 1\)（地面にいる状態が \(1\) 通り）で初期化する。
3. \(i = 1\) から \(N\) まで順に以下を行う：
   • \(i\) が壊れている段なら \(dp[i] = 0\) とする。
   • そうでなければ \(dp[i] = dp[i-1] + dp[i-2] + dp[i-3]\)（ただし添字が \(0\) 未満の項は加えない）を \(10^9 + 7\) で割った余りとして計算する。
4. \(dp[N]\) を出力する。

計算量

• 時間計算量: \(O(N + M)\)（壊れた段の集合構築に \(O(M)\)、DPのループに \(O(N)\)）
• 空間計算量: \(O(N + M)\)（DP配列に \(O(N)\)、壊れた段の集合に \(O(M)\)）

実装のポイント

• 壊れている段の判定を高速に行うため、リストではなく 集合（set） を使う。リストの in 演算は \(O(M)\) だが、集合なら平均 \(O(1)\)。

• \(M = 0\) の場合は \(2\) 行目が与えられない可能性があるため、入力を一括で読み込んで split() する方式が安全。

• \(i < 2\) や \(i < 3\) のとき存在しない添字を参照しないよう、条件分岐でガードする。

• 答えが非常に大きくなるため、毎回 \(10^9 + 7\) で余りを取ることを忘れない。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    broken = set()
    for i in range(M):
        broken.add(int(input_data[idx])); idx += 1
    
    MOD = 10**9 + 7
    
    dp = [0] * (N + 1)
    dp[0] = 1
    
    for i in range(1, N + 1):
        if i in broken:
            dp[i] = 0
        else:
            dp[i] = dp[i - 1]
            if i >= 2:
                dp[i] += dp[i - 2]
            if i >= 3:
                dp[i] += dp[i - 3]
            dp[i] %= MOD
    
    print(dp[N])

main()

この解説は claude4.6opus-thinking によって生成されました。