概要

\(N\) 段の階段を、1回の移動で1, 2, 3段上ることができるが、いくつかの段が壊れているときに、0段目から\(N\)段目に到達する方法の数を求める問題。

考察

この問題は典型的な動的計画法（DP）の応用例です。

まず、壊れていない段に対して「その段にたどり着く方法の数」を順番に計算していけば良さそうです。例えば、ある段 \(i\) にたどり着くには、\(i-1\), \(i-2\), \(i-3\) 段目から来る方法があります。したがって、以下のような遷移が考えられます：

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

ただし、\(i\) が壊れている段であれば、その段には到達できないので \(dp[i] = 0\) とする必要があります。

また、壊れた段があっても、それらを飛び越えて移動できる点に注意が必要です。つまり、壊れた段に止まることは禁止されているだけで、そこを通過することは可能です。

例えば、段 2 が壊れている場合でも、段 0 から段 3 へ直接移動することは可能です。

このように、「前の状態から次の状態への遷移」を考えるタイプの問題は DP を使うことで効率的に解けます。

素朴な再帰で求めると指数時間になってしまうため、DPによるボトムアップ的なアプローチが必要になります。

アルゴリズム

動的計画法（Dynamic Programming）を用います。

• dp[i]：\(i\) 段目にたどり着く方法の数
• 初期条件：dp[0] = 1（地面にいるのは1通り）
• 遷移：
  • 各段 \(i = 1\) から \(N\) について：
    • もし \(i\) が壊れているなら continue
    • そうでなければ、\(i-1\), \(i-2\), \(i-3\) から遷移可能なので： $\( dp[i] = (dp[i] + dp[i - 1] + dp[i - 2] + dp[i - 3]) \bmod (10^9 + 7) \)$

最終的に求めたいのは dp[N] です。

壊れている段は事前に set に入れておくことで、各段について \(O(1)\) で確認できます。

計算量

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

\(N\) が最大 \(10^5\) なので、十分高速です。

実装のポイント

• 壊れている段を set で持っておくと、存在判定が高速に行える。

• DPテーブルはインデックス \(0\) から \(N\) まで確保する。

• 各段について、過去3つ分のDP値を参照する際に、範囲外アクセスに注意する（i - step >= 0）。

• 最終結果は dp[N]。

  ソースコード

MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    if M == 0:
        broken = set()
        idx = 2
    else:
        broken = set(map(int, data[2:2+M]))
        idx = 2 + M
    
    # dp[i] := i段目に到達する方法の数
    dp = [0] * (N + 1)
    dp[0] = 1
    
    for i in range(1, N + 1):
        if i in broken:
            continue
        for step in [1, 2, 3]:
            if i - step >= 0:
                dp[i] = (dp[i] + dp[i - step]) % MOD
    
    print(dp[N])

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。