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)と呼ばれ、この問題に非常に適しています。
アルゴリズム
動的計画法を用いて、以下のように計算を進めます。
- DPテーブルの定義:
dp[i]を「\(i\) 段目に到達する登り方の総数」とします。配列のサイズは \(N+1\) です。 - 初期状態の設定:
スタート地点である 0 段目には「何もしていない」という 1 通りの状態があると考え、
dp[0] = 1とします。 - 遷移(計算式):
\(i = 1\) から \(N\) まで順番に以下の処理を行います。
- もし \(i\) 段目が塗装中(
S[i-1] == '#')なら、dp[i] = 0とします。 - そうでないなら、
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]とします。 ※ \(i < 3\) の場合に負のインデックスを参照しないよう注意が必要です。
- もし \(i\) 段目が塗装中(
- 余りの計算: 数値が非常に大きくなる可能性があるため、加算するたびに \(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 によって生成されました。
投稿日時:
最終更新: