公式

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

Gemini 3.0 Flash (Thinking)

概要

この問題は、\(N\) 段の階段を 1 段、2 段、または 3 段ずつ登る際、特定の「止まれない段」を避けながら \(N\) 段目に到達するまでの経路の総数を求める問題です。

考察

この問題のポイントは、「ある段に到達する方法は、その直前の状態から決まる」という点にあります。

高橋君が \(i\) 段目に到達する直前の状態は、以下の 3 通りしかありません。 1. \((i-1)\) 段目から 1 段登る 2. \((i-2)\) 段目から 2 段登る 3. \((i-3)\) 段目から 3 段登る

したがって、\(i\) 段目に到達する登り方の総数は、「\((i-1)\) 段目、\((i-2)\) 段目、\((i-3)\) 段目それぞれの到達方法の合計」となります。ただし、その段が塗装中(#)である場合は、そこに止まることはできないため、到達する方法は 0 通りとして計算する必要があります。

このように、小さな部分問題(手前の段への到達数)の解を利用して大きな問題(現在の段への到達数)を解く手法は動的計画法(DP)と呼ばれ、この問題に非常に適しています。

アルゴリズム

動的計画法を用いて、以下のように計算を進めます。

  1. DPテーブルの定義: dp[i] を「\(i\) 段目に到達する登り方の総数」とします。配列のサイズは \(N+1\) です。
  2. 初期状態の設定: スタート地点である 0 段目には「何もしていない」という 1 通りの状態があると考え、dp[0] = 1 とします。
  3. 遷移(計算式): \(i = 1\) から \(N\) まで順番に以下の処理を行います。
    • もし \(i\) 段目が塗装中(S[i-1] == '#')なら、dp[i] = 0 とします。
    • そうでないなら、dp[i] = dp[i-1] + dp[i-2] + dp[i-3] とします。 ※ \(i < 3\) の場合に負のインデックスを参照しないよう注意が必要です。
  4. 余りの計算: 数値が非常に大きくなる可能性があるため、加算するたびに \(10^9 + 7\) で割った余りを取ります。

最終的な答えは dp[N] となります。

計算量

  • 時間計算量: \(O(N)\) \(1\) 段目から \(N\) 段目までを 1 回ずつループで計算するため、段数 \(N\) に比例した時間で計算が終わります。\(N=10^5\) であっても十分高速に動作します。
  • 空間計算量: \(O(N)\) 各段の状態を記録するための配列 dp のサイズが \(N+1\) であるため、空間計算量も \(N\) に比例します。

実装のポイント

  • インデックスのズレ: 文字列 S は 0 番目の文字が 1 段目を表しているため、i 段目の状態を確認する際は S[i-1] を参照する必要があります。

  • モジュロ演算: 合計を計算する際、最後にまとめて余りを取るのではなく、各ステップで余りを取ることでオーバーフローを防ぎます(Pythonの場合は自動で多倍長整数を扱いますが、競技プログラミングの習慣として重要です)。

  • 初期化: 階段を登れない段(#)の dp の値を 0 にすることで、それ以降の段の計算に「その段を経由するルート」が正しく加算されないようになります。

    ソースコード

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

この解説は gemini-3-flash-thinking によって生成されました。

投稿日時:
最終更新: