概要

壊れた段を避けながら、1段、2段、または3段ずつ進める場合の階段の上り方の総数を求める動的計画法の問題です。

考察

この問題は「壊れた段を踏まない」という制約付きの階段上り問題です。重要な観察点は以下の通りです：

1. 各段iへの到達方法は、1段前(i-1)、2段前(i-2)、3段前(i-3)からの移動の和で計算できる
2. 壊れた段には到達できないため、その段の通り数は0となる
3. 壊れた段を飛び越えることは可能（途中で着地しない限り問題ない）
4. Nが最大10^5まで大きくなるため、効率的なアルゴリズムが必要

素朴な再帰的アプローチでは計算量が指数関数的になり、N=10^5では到底処理できません。動的計画法を用いることで、各段の通り数を一度だけ計算する効率的な解法が実現できます。

アルゴリズム

動的計画法を用いて、各段iへの到達方法の総数をdp[i]として計算します：

1. dp[0] = 1（初期状態：地面に立っている）
2. 各段i (1 ≤ i ≤ N)について：
   • iが壊れた段ならdp[i] = 0
   • それ以外の場合：dp[i] = dp[i-1] + dp[i-2] + dpi-3
3. 最終的にdp[N]が答えとなる

ただし、i-1, i-2, i-3が範囲外の場合は加算しないように注意します。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

1. 壊れた段の集合をsetで保持し、高速な存在チェックを行う

2. MOD演算を忘れずに行う（答えが非常に大きくなるため）

3. 配列のインデックス範囲に注意する（0段目からN段目まで）

4. M=0の場合の入力処理に注意する（2行目が存在しない可能性がある）

   ソースコード

MOD = 10**9 + 7

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    n = int(data[0])
    m = int(data[1])
    broken = set()
    if m > 0:
        for i in range(2, 2 + m):
            broken.add(int(data[i]))
            
    dp = [0] * (n + 1)
    dp[0] = 1
    
    for i in range(1, n + 1):
        if i in broken:
            dp[i] = 0
            continue
        if i - 1 >= 0:
            dp[i] = (dp[i] + dp[i - 1]) % MOD
        if i - 2 >= 0:
            dp[i] = (dp[i] + dp[i - 2]) % MOD
        if i - 3 >= 0:
            dp[i] = (dp[i] + dp[i - 3]) % MOD
            
    print(dp[n] % MOD)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。