C - 階段を登る方法 / Ways to Climb Stairs 解説 by admin
Claude 4.5 Opus概要
\(N\) 段の階段を、1段・2段・3段のいずれかで登っていき、塗装中の段を避けながら \(N\) 段目に到達する方法の数を求める動的計画法(DP)の問題です。
考察
問題の本質を理解する
まず、塗装中の段がない場合を考えてみましょう。\(i\) 段目に到達する方法は、以下の3パターンがあります:
- \((i-1)\) 段目から 1段 登る
- \((i-2)\) 段目から 2段 登る
- \((i-3)\) 段目から 3段 登る
つまり、\(i\) 段目に到達する方法の数は、「\((i-1)\) 段目に到達する方法の数」+「\((i-2)\) 段目に到達する方法の数」+「\((i-3)\) 段目に到達する方法の数」となります。
素朴なアプローチの問題点
全ての登り方を列挙しようとすると、\(N\) が大きい場合に組み合わせが爆発的に増えます(指数的に増加)。例えば \(N = 100\) でも、方法の数は天文学的な数になり、時間内に解けません。
動的計画法による解決
「\(i\) 段目に到達する方法の数」は、直前の数段の情報だけから計算できます。この性質を利用して、小さい段から順に方法の数を計算していけば、効率的に答えが求まります。
塗装中の段の扱い
塗装中(#)の段では「止まれない」ので、その段に到達する方法の数は \(0\) です。飛び越えることは可能なので、その段を経由しない遷移は問題ありません。
アルゴリズム
- 配列 \(dp\) を用意し、\(dp[i]\) で「\(i\) 段目に到達する方法の数」を管理します
- 初期条件として \(dp[0] = 1\)(地面にいる状態が1通り)
- \(i = 1\) から \(N\) まで順に以下を計算:
- \(S[i-1]\) が
#なら \(dp[i] = 0\)(止まれない) - そうでなければ \(dp[i] = dp[i-1] + dp[i-2] + dp[i-3]\)(存在する範囲のみ加算)
- \(S[i-1]\) が
- 最終的に \(dp[N]\) が答え
具体例(N = 4, S = “.#..“)
| 段 | 状態 | 計算 | \(dp[i]\) |
|---|---|---|---|
| 0 | 地面 | 初期値 | 1 |
| 1 | . |
\(dp[0] = 1\) | 1 |
| 2 | # |
塗装中 | 0 |
| 3 | . |
\(dp[2] + dp[1] + dp[0] = 0 + 1 + 1\) | 2 |
| 4 | . |
\(dp[3] + dp[2] + dp[1] = 2 + 0 + 1\) | 3 |
答えは \(3\) 通り(0→1→3→4、0→1→4、0→3→4)です。
計算量
- 時間計算量: \(O(N)\)
- 各段について定数回の演算を行うため
- 空間計算量: \(O(N)\)
- DP配列のサイズ
実装のポイント
インデックスのずれに注意: 文字列 \(S\) は0-indexedなので、\(i\) 段目の状態は \(S[i-1]\) で参照します
境界条件の処理: \(i < 1, 2, 3\) の場合、存在しない段を参照しないよう条件分岐が必要です
MODの取り方: 方法の数は非常に大きくなるため、加算のたびに \(10^9 + 7\) で割った余りを取ります
初期状態の設定: 「地面(0段目)にいる」という状態を \(dp[0] = 1\) として表現するのがポイントです
ソースコード
def solve():
MOD = 10**9 + 7
N = int(input())
S = input().strip()
# dp[i] = i段目に到達する方法の数
# 0段目(地面)からスタート
dp = [0] * (N + 1)
dp[0] = 1 # 地面からスタート
for i in range(1, N + 1):
# i段目が塗装中(#)なら止まれないのでスキップ
if S[i - 1] == '#':
dp[i] = 0
continue
# 1段前、2段前、3段前から来る場合を合計
if i >= 1:
dp[i] = (dp[i] + dp[i - 1]) % MOD
if i >= 2:
dp[i] = (dp[i] + dp[i - 2]) % MOD
if i >= 3:
dp[i] = (dp[i] + dp[i - 3]) % MOD
print(dp[N])
solve()
この解説は claude4.5opus によって生成されました。