Official

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

GPT 5.2 High

Overview

On a staircase where you can advance \(1, 2, 3\) steps at a time, count the number of ways to reach step \(N\) while avoiding steps that cannot be stopped on (#), using dynamic programming to find the result modulo \(10^9+7\).

Analysis

The only ways to reach each step \(i\) are “coming from 1 step before, 2 steps before, or 3 steps before.” In other words, the answer for each step can be constructed from the answers of the previous 3 steps.

  • Naively “enumerating all climbing patterns” would cause the number of branches to increase by up to 3 at each step, leading to an exponential number of ways, which is far too slow for \(N \le 10^5\) (TLE).
  • Also, steps under construction (#) “can be passed through but cannot be stopped on,” so we must not count those steps as reachable destinations. Handling this carelessly leads to WA.

Therefore, by using DP (dynamic programming) that sequentially computes “the number of ways to reach each step,” we only need to process each step once.

As a concrete example, when step \(i\) is .: - Go up 1 step from step \(i-1\) - Go up 2 steps from step \(i-2\) - Go up 3 steps from step \(i-3\)

We simply add up these 3 “ways of arriving.” If the step is #, we set \(dp[i]=0\).

Algorithm

Define \(dp[i]\) as “the number of ways to reach and stop at step \(i\).”

  • Initial value: We are on the ground (step 0) in exactly 1 way, so \(dp[0]=1\)
  • Transition:
    • If \(S[i] = \#\) (step \(i\) is under construction), we cannot stop there, so \(dp[i]=0\)
    • Otherwise (.): \(dp[i] = dp[i-1] + dp[i-2] + dp[i-3]\) (only for indices that exist)
  • Since values can become large, take mod \(10^9+7\) at each computation.

The string \(S\) is given in 0-index for 1-indexed step numbers, so the state of step \(i\) is checked by looking at S[i-1].

Complexity

  • Time complexity: \(O(N)\) (a constant number of additions per step)
  • Space complexity: \(O(N)\) (storing the array \(dp\))

Implementation Notes

  • Since S is 0-indexed, note that the check for step \(i\) uses S[i-1].

  • Steps with # “can be passed through but cannot be stopped on,” so as a transition destination they are treated as 0 (dp[i]=0).

  • When \(i<2\) or \(i<3\), avoid referencing dp[i-2] or dp[i-3] by using conditional branches like if i >= 2.

  • The final answer is dp[N]. According to the problem statement, step \(N\) is always ., so there is no need to check reachability.

    Source Code

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()

This editorial was generated by gpt-5.2-high.