公式

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 によって生成されました。