公式

C - 階段を登る方法 / Ways to Climb Stairs 解説 by admin 印刷ページ

Claude 4.5 Opus

Overview

This is a dynamic programming (DP) problem where you climb a staircase of \(N\) steps using steps of 1, 2, or 3 at a time, and you need to find the number of ways to reach step \(N\) while avoiding steps that are being painted.

Analysis

Understanding the Essence of the Problem

First, let’s consider the case where there are no painted steps. There are 3 patterns to reach step \(i\):

  1. Climb 1 step from step \((i-1)\)
  2. Climb 2 steps from step \((i-2)\)
  3. Climb 3 steps from step \((i-3)\)

In other words, the number of ways to reach step \(i\) equals “the number of ways to reach step \((i-1)\)” + “the number of ways to reach step \((i-2)\)” + “the number of ways to reach step \((i-3)\)”.

Problems with the Naive Approach

If we try to enumerate all possible ways to climb, the number of combinations explodes when \(N\) is large (exponential growth). For example, even at \(N = 100\), the number of ways becomes astronomically large and cannot be solved within the time limit.

Solving with Dynamic Programming

“The number of ways to reach step \(i\)” can be computed using only the information from a few preceding steps. By leveraging this property and computing the number of ways sequentially from smaller steps, we can efficiently find the answer.

Handling Painted Steps

You “cannot stop” on a painted (#) step, so the number of ways to reach that step is \(0\). However, jumping over it is possible, so transitions that do not pass through that step are fine.

Algorithm

  1. Prepare an array \(dp\), where \(dp[i]\) represents “the number of ways to reach step \(i\)”
  2. Set the initial condition as \(dp[0] = 1\) (there is exactly 1 way to be on the ground)
  3. For \(i = 1\) to \(N\), compute the following:
    • If \(S[i-1]\) is #, then \(dp[i] = 0\) (cannot stop here)
    • Otherwise, \(dp[i] = dp[i-1] + dp[i-2] + dp[i-3]\) (only add terms that exist within valid range)
  4. The final answer is \(dp[N]\)

Concrete Example (N = 4, S = “.#..”)

Step State Calculation \(dp[i]\)
0 Ground Initial value 1
1 . \(dp[0] = 1\) 1
2 # Being painted 0
3 . \(dp[2] + dp[1] + dp[0] = 0 + 1 + 1\) 2
4 . \(dp[3] + dp[2] + dp[1] = 2 + 0 + 1\) 3

The answer is \(3\) ways (0→1→3→4, 0→1→4, 0→3→4).

Complexity

  • Time complexity: \(O(N)\)
    • A constant number of operations is performed for each step
  • Space complexity: \(O(N)\)
    • Size of the DP array

Implementation Notes

  1. Be careful with index offsets: Since the string \(S\) is 0-indexed, the state of step \(i\) is referenced by \(S[i-1]\)

  2. Handling boundary conditions: When \(i < 1, 2, 3\), conditional branching is needed to avoid referencing non-existent steps

  3. Taking MOD: Since the number of ways can become extremely large, take the remainder modulo \(10^9 + 7\) after each addition

  4. Setting the initial state: The key point is to represent “being on the ground (step 0)” as \(dp[0] = 1\)

    Source Code

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

This editorial was generated by claude4.5opus.

投稿日時:
最終更新: