公式

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

Claude 4.5 Opus

概要

\(N\) 段の階段を、1段・2段・3段のいずれかで登っていき、塗装中の段を避けながら \(N\) 段目に到達する方法の数を求める動的計画法(DP)の問題です。

考察

問題の本質を理解する

まず、塗装中の段がない場合を考えてみましょう。\(i\) 段目に到達する方法は、以下の3パターンがあります:

  1. \((i-1)\) 段目から 1段 登る
  2. \((i-2)\) 段目から 2段 登る
  3. \((i-3)\) 段目から 3段 登る

つまり、\(i\) 段目に到達する方法の数は、「\((i-1)\) 段目に到達する方法の数」+「\((i-2)\) 段目に到達する方法の数」+「\((i-3)\) 段目に到達する方法の数」となります。

素朴なアプローチの問題点

全ての登り方を列挙しようとすると、\(N\) が大きい場合に組み合わせが爆発的に増えます(指数的に増加)。例えば \(N = 100\) でも、方法の数は天文学的な数になり、時間内に解けません。

動的計画法による解決

「\(i\) 段目に到達する方法の数」は、直前の数段の情報だけから計算できます。この性質を利用して、小さい段から順に方法の数を計算していけば、効率的に答えが求まります。

塗装中の段の扱い

塗装中(#)の段では「止まれない」ので、その段に到達する方法の数は \(0\) です。飛び越えることは可能なので、その段を経由しない遷移は問題ありません。

アルゴリズム

  1. 配列 \(dp\) を用意し、\(dp[i]\) で「\(i\) 段目に到達する方法の数」を管理します
  2. 初期条件として \(dp[0] = 1\)(地面にいる状態が1通り)
  3. \(i = 1\) から \(N\) まで順に以下を計算:
    • \(S[i-1]\) が # なら \(dp[i] = 0\)(止まれない)
    • そうでなければ \(dp[i] = dp[i-1] + dp[i-2] + dp[i-3]\)(存在する範囲のみ加算)
  4. 最終的に \(dp[N]\) が答え

具体例(N = 4, S = “.#..“)

段 状態 計算 \(dp[i]\)
0 地面 初期値 1
1 . \(dp[0] = 1\) 1
2 # 塗装中 0
3 . \(dp[2] + dp[1] + dp[0] = 0 + 1 + 1\) 2
4 . \(dp[3] + dp[2] + dp[1] = 2 + 0 + 1\) 3

答えは \(3\) 通り(0→1→3→4、0→1→4、0→3→4)です。

計算量

  • 時間計算量: \(O(N)\)
    • 各段について定数回の演算を行うため
  • 空間計算量: \(O(N)\)
    • DP配列のサイズ

実装のポイント

  1. インデックスのずれに注意: 文字列 \(S\) は0-indexedなので、\(i\) 段目の状態は \(S[i-1]\) で参照します

  2. 境界条件の処理: \(i < 1, 2, 3\) の場合、存在しない段を参照しないよう条件分岐が必要です

  3. MODの取り方: 方法の数は非常に大きくなるため、加算のたびに \(10^9 + 7\) で割った余りを取ります

  4. 初期状態の設定: 「地面(0段目)にいる」という状態を \(dp[0] = 1\) として表現するのがポイントです

    ソースコード

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

この解説は claude4.5opus によって生成されました。

投稿日時:
最終更新: