Official

C - 階段を登る方法 / Ways to Climb Stairs Editorial by admin

Qwen3-Coder-480B

概要

\(N\) 段の階段を、1回に1段、2段、または3段登ることができ、一部の段では止まれない制約下で、最終的に最上段に到達する方法の総数を求める問題です。

考察

この問題は典型的な動的計画法(DP)で解くことができます。

まず、制約がない場合、\(i\) 段目に到達する方法の数は、
$\( \text{dp}[i] = \text{dp}[i-1] + \text{dp}[i-2] + \text{dp}[i-3] \)$ のように表せます。これは、1段前、2段前、3段前からそれぞれ1回のジャンプで到達できるためです。

しかし、今回の問題では「特定の段で止まることができない」つまり # の段には立ち入れません。そのため、その段に対応する \(\text{dp}[i]\) は更新してはいけません。

具体的には: - もし \(S[i-1] == \text{`#'}\) なら、その段には止まれないので \(\text{dp}[i] = 0\) のままにする。 - そうでない(.)なら、通常通り遷移を行う。

また、初期条件として \(\text{dp}[0] = 1\) とします。これは「地面からスタートする1通りの方法がある」と考えています。

このようにして、最終的に \(\text{dp}[N]\) が求める答えになります。

アルゴリズム

動的計画法(DP)を使用します。

  • \(\text{dp}[i]\):\(i\) 段目に到達する方法の数
  • 初期化:\(\text{dp}[0] = 1\)
  • 更新:
    • 各段 \(i = 1\) から \(N\) について、
      • もし \(S[i-1] == \text{`#\'}\) なら、スキップ
      • そうでなければ、 $\( \text{dp}[i] = (\text{dp}[i] + \text{dp}[i-1] + \text{dp}[i-2] + \text{dp}[i-3]) \bmod (10^9+7) \)$ (ただし、インデックスが負にならない範囲)

このようにして、最終的に \(\text{dp}[N]\) を出力すればよいです。

例

例えば、\(N=4\), \(S=\text{"..#."}\) の場合、

段 状態 dp値
0 - 1
1 . 1
2 . 2
3 # 0
4 . 3

よって答えは \(3\) 通りです。

計算量

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

各段に対して定数時間の操作しか行わないため、線形時間で解けます。配列も \(N+1\) 個だけ使用するので、空間も線形です。

実装のポイント

  • 文字列 \(S\) のインデックスは0始まりなので、\(i\) 段目に対応するのは \(S[i-1]\) です。
  • 答えは \(10^9+7\) で割った余りを出力する必要があるため、適宜 mod を取りましょう。
  • DPテーブルは最初にすべて 0 で初期化し、\(\text{dp}[0] = 1\) とするのがポイントです。
## ソースコード

```python
MOD = 10**9 + 7

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

if __name__ == "__main__":
    main()

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