公式

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

Gemini 3.0 Flash (Thinking)

Overview

This problem asks us to find the total number of ways to reach step \(N\) of a staircase with \(N\) steps, where you can climb 1, 2, or 3 steps at a time, while avoiding certain “unpassable steps.”

Analysis

The key insight of this problem is that “the number of ways to reach a given step is determined by the states immediately before it.”

There are only 3 possible states immediately before Takahashi reaches step \(i\): 1. Climbing 1 step from step \((i-1)\) 2. Climbing 2 steps from step \((i-2)\) 3. Climbing 3 steps from step \((i-3)\)

Therefore, the total number of ways to reach step \(i\) is “the sum of the number of ways to reach step \((i-1)\), step \((i-2)\), and step \((i-3)\).” However, if a step is under construction (#), it is impossible to stop there, so the number of ways to reach that step must be calculated as 0.

This approach of solving a larger problem (number of ways to reach the current step) by utilizing solutions to smaller subproblems (number of ways to reach earlier steps) is called dynamic programming (DP), and it is extremely well-suited for this problem.

Algorithm

Using dynamic programming, we proceed with the computation as follows:

  1. DP Table Definition: Let dp[i] be “the total number of ways to reach step \(i\).” The array size is \(N+1\).
  2. Initial State Setup: We consider the starting point, step 0, as having 1 way (the state of “having done nothing”), so we set dp[0] = 1.
  3. Transition (Recurrence Relation): For each \(i\) from \(1\) to \(N\), perform the following:
    • If step \(i\) is under construction (S[i-1] == '#'), set dp[i] = 0.
    • Otherwise, set dp[i] = dp[i-1] + dp[i-2] + dp[i-3]. ※ Be careful not to reference negative indices when \(i < 3\).
  4. Modular Arithmetic: Since the values can become extremely large, take the remainder modulo \(10^9 + 7\) after each addition.

The final answer is dp[N].

Complexity

  • Time Complexity: \(O(N)\) Since we compute each step from step \(1\) to step \(N\) exactly once in a loop, the computation finishes in time proportional to the number of steps \(N\). Even for \(N=10^5\), this runs sufficiently fast.
  • Space Complexity: \(O(N)\) Since the array dp used to store the state of each step has size \(N+1\), the space complexity is also proportional to \(N\).

Implementation Notes

  • Index Offset: Since the 0th character of string S represents step 1, when checking the state of step \(i\), you need to reference S[i-1].

  • Modulo Operation: When computing sums, instead of taking the remainder all at once at the end, take the remainder at each step to prevent overflow (in Python, arbitrary-precision integers are handled automatically, but this is an important practice in competitive programming).

  • Initialization: By setting the dp value of unclimbable steps (#) to 0, we ensure that routes passing through those steps are correctly not added to the calculations for subsequent steps.

    Source Code

import sys

def main():
    # 入力を読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    s = input_data[1]
    
    # 答えを割る余り
    MOD = 10**9 + 7
    
    # dp[i] は i 段目に到達する登り方の総数
    dp = [0] * (n + 1)
    
    # スタート地点(0段目)は1通り
    dp[0] = 1
    
    for i in range(1, n + 1):
        # s は 0-indexed なので、i 段目の状態は s[i-1]
        if s[i-1] == '#':
            # 塗装中の段には止まれない
            dp[i] = 0
        else:
            # i-1, i-2, i-3 段目から 1, 2, 3 段登って到達可能
            total_ways = 0
            if i >= 1:
                total_ways += dp[i-1]
            if i >= 2:
                total_ways += dp[i-2]
            if i >= 3:
                total_ways += dp[i-3]
            
            # 余りをとる
            dp[i] = total_ways % MOD
            
    # N 段目に到達する登り方を出力
    print(dp[n])

if __name__ == "__main__":
    main()

This editorial was generated by gemini-3-flash-thinking.