概要

この問題は、1歩で1〜3段進めるという条件のもと、特定の「壊れた段」を避けながら \(N\) 段目まで到達する経路の総数を求める問題です。

考察

1. 状態の遷移を考える

ある段 \(i\) に到達するためには、その直前にどの段にいたかを考えます。問題のルールから、以下の3つの可能性があります。 - \(i-1\) 段目から1段上る - \(i-2\) 段目から2段上る - \(i-3\) 段目から3段上る

したがって、\(i\) 段目に到達する方法の数は、「\(i-1, i-2, i-3\) 段目に到達する方法の数の合計」になります。

2. 壊れた段の扱い

もし \(i\) 段目が壊れている場合、そこに「着地」することはできません。つまり、壊れている段に到達する方法の数は 0 通りとして扱う必要があります。

3. 動的計画法（DP）の適用

「現在の状態が過去の状態の積み重ねで決まる」という性質は、動的計画法（DP）が非常に有効です。 単純な再帰関数で計算しようとすると、同じ段数の計算を何度も繰り返すことになり、計算量が爆発的に増えてしまいます（\(N=10^5\) では間に合いません）。しかし、小さい段数から順番に結果を記録（メモ化）していくことで、効率よく計算できます。

アルゴリズム

動的計画法の手順

1. DPテーブルの定義: dp[i] を「\(i\) 段目に到達する方法の数」と定義します。配列のサイズは \(N+1\) です。
2. 初期値の設定:
   • 地面（0段目）にいる方法は「何もしない」という 1 通りなので、dp[0] = 1 とします。
3. 壊れた段の事前処理:
   • 壊れている段の番号を高速に判定できるように、サイズ \(N+1\) の真偽値配列 is_broken を作成しておきます。
4. 遷移式の計算: \(i = 1\) から \(N\) まで順番に以下を計算します。
   • もし is_broken[i] が真なら、dp[i] = 0
   • そうでなければ、dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % (10^9 + 7) （※ \(i-2\) や \(i-3\) が 0 未満にならないよう注意します）

最後に dp[N] の値が答えとなります。

計算量

• 時間計算量: \(O(N)\)
  • 壊れた段の記録に \(O(M)\)、1段目から \(N\) 段目までのループに \(O(N)\) かかります。\(M \leq N\) なので、全体で \(O(N)\) となり、制約の \(N=10^5\) に対して十分に高速です。
• 空間計算量: \(O(N)\)
  • DPテーブルおよび壊れた段を管理する配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 大きな数の処理: 答えが非常に大きくなるため、計算の各ステップで \(10^9 + 7\) の余りをとるようにします。Pythonは多倍長整数を扱えますが、余りをこまめにとることで計算速度の低下を防げます。

• 入力の高速化: \(N\) や \(M\) が大きいため、sys.stdin.read().split() などを用いて一括で入力を取得すると効率的です。

• 境界条件: \(i=1\) や \(i=2\) のときに dp[i-2] や dp[i-3] を参照してインデックスエラーにならないよう、条件分岐で制御します。

  ソースコード

import sys

def solve():
    # 入力を一括で取得して分割
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 階段の段数, M: 壊れている段の数
    n = int(input_data[0])
    m = int(input_data[1])
    
    # 壊れている段を記録する配列（高速アクセスのため）
    is_broken = [False] * (n + 1)
    if m > 0:
        for i in range(m):
            broken_step = int(input_data[2 + i])
            is_broken[broken_step] = True
            
    # DPテーブルの初期化
    # dp[i] は i段目に到達する方法の数
    dp = [0] * (n + 1)
    dp[0] = 1 # 地面（0段目）にいる方法は1通り
    
    MOD = 10**9 + 7
    
    # 1段目からN段目まで順番に計算
    for i in range(1, n + 1):
        if is_broken[i]:
            dp[i] = 0
            continue
        
        # 1歩前、2歩前、3歩前から到達可能
        ways = dp[i-1]
        if i >= 2:
            ways += dp[i-2]
        if i >= 3:
            ways += dp[i-3]
        
        # 10^9 + 7 で割った余りを格納
        dp[i] = ways % MOD
        
    # N段目に到達する方法の数を出力
    print(dp[n])

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。