公式
C - 階段を登る方法 / Ways to Climb Stairs 解説 by admin
GPT 5.2 High概要
1 回に \(1,2,3\) 段進める階段で、止まれない段(#)を避けつつ \(N\) 段目に到達する通り数を、動的計画法で数えて \(10^9+7\) で割った余りを求めます。
考察
各段 \(i\) に到達する方法は「直前の 1 段前・2 段前・3 段前から来る」しかありません。つまり、段ごとの答えは直前 3 つの段の答えから作れます。
- 素朴に「全ての登り方を列挙」すると、分岐が最大 3 つずつ増えるため通り数が指数的に増え、\(N \le 10^5\) では到底間に合いません(TLE)。
- また、塗装中の段(
#)は「通過はできるが止まれない」ので、その段を到達先として数えない必要があります。ここを雑に扱うと WA になります。
そこで、「各段に到達する通り数」を順番に計算する DP(動的計画法)にすると、各段を 1 回ずつ処理するだけで済みます。
具体例として、\(i\) 段目が . のとき
- \(i-1\) 段目から 1 段上がる
- \(i-2\) 段目から 2 段上がる
- \(i-3\) 段目から 3 段上がる
の 3 通りの「来方」を足し合わせればよい、という形になります。# なら \(dp[i]=0\) にします。
アルゴリズム
\(dp[i]\) を「\(i\) 段目に到達して止まる通り数」と定義します。
- 初期値: 地面(0 段目)には 1 通りでいるので \(dp[0]=1\)
- 遷移:
- もし \(S[i] = \#\)(\(i\) 段目が塗装中)なら止まれないので \(dp[i]=0\)
- そうでなければ(
.)
\(dp[i] = dp[i-1] + dp[i-2] + dp[i-3]\)(存在する範囲のみ)
- 各計算は大きくなるので毎回 \(10^9+7\) で mod を取ります。
文字列 \(S\) は 1-index の段番号に対して 0-index で与えられるので、段 \(i\) の状態は S[i-1] を見ます。
計算量
- 時間計算量: \(O(N)\)(各段で定数回の足し算)
- 空間計算量: \(O(N)\)(配列 \(dp\) を保持)
実装のポイント
Sは 0-index なので、段 \(i\) の判定はS[i-1]に注意する。#の段は「通過は OK だが止まれない」ため、遷移で足し込む先としては 0 扱い(dp[i]=0)にする。\(i<2\) や \(i<3\) のときに
dp[i-2],dp[i-3]を参照しないよう、if i >= 2のように条件分岐する。最終的な答えは
dp[N]。問題文より \(N\) 段目は必ず.なので到達可能性の判定は不要です。ソースコード
import sys
MOD = 10**9 + 7
def main():
input = sys.stdin.readline
N = int(input().strip())
S = input().strip()
dp = [0] * (N + 1)
dp[0] = 1
for i in range(1, N + 1):
if S[i - 1] == '#':
dp[i] = 0
continue
val = dp[i - 1]
if i >= 2:
val += dp[i - 2]
if i >= 3:
val += dp[i - 3]
dp[i] = val % MOD
print(dp[N] % MOD)
if __name__ == "__main__":
main()
この解説は gpt-5.2-high によって生成されました。