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) \)$ (ただし、インデックスが負にならない範囲)
- 各段 \(i = 1\) から \(N\) について、
このようにして、最終的に \(\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 によって生成されました。