Official

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

DeepSeek V3

概要

高橋君が1段から3段まで登れる階段で、塗装中の段を避けながら最上段に到達する方法の数を求める動的計画法の問題です。

考察

この問題は典型的な動的計画法(DP)問題の変種です。通常の階段登り問題では、各段に到達する方法の数を1,2,3段前の値の和で計算しますが、今回は「塗装中の段には止まれない」という制約が追加されています。

素朴な再帰的アプローチでは、各段で3通りの選択肢があるため計算量が\(O(3^N)\)となり、\(N\)が最大\(10^5\)の場合には到底計算できません。そこで、動的計画法を用いて効率的に計算する必要があります。

アルゴリズム

動的計画法を用いて、各段iに到達する方法の数をdp[i]として計算します。具体的には以下の手順です:

  1. dp[0] = 1(地面からスタート)
  2. i=1からNまで順に処理:
    • もし段iが塗装中(S[i-1] == ‘#‘)なら、dp[i] = 0(ここには止まれない)
    • そうでなければ、dp[i] = dp[i-1] + dp[i-2] + dp[i-3](1,2,3段前から到達可能)

ただし、i-1, i-2, i-3が負のインデックスにならないように注意します。最終的にdp[N]が求める答えとなります。

計算量

  • 時間計算量: \(O(N)\)
  • 空間計算量: \(O(N)\)

実装のポイント

  1. MOD値(\(10^9 + 7\))で割った余りを保持する

  2. 文字列Sのインデックスとdp配列のインデックスに1のズレがある(Sは0-indexed、段番号は1-indexed)

  3. 範囲外アクセスを防ぐために、i-1, i-2, i-3が0以上であることを確認してから加算する

  4. 塗装中の段ではdp値を0にリセットする(continueでスキップ)

    ソースコード

MOD = 10**9 + 7

def main():
    import sys
    data = sys.stdin.read().splitlines()
    n = int(data[0].strip())
    S = data[1].strip()
    
    dp = [0] * (n + 1)
    dp[0] = 1
    
    for i in range(1, n + 1):
        if S[i - 1] == '#':
            continue
            
        if i - 1 >= 0:
            dp[i] = (dp[i] + dp[i - 1]) % MOD
        if i - 2 >= 0:
            dp[i] = (dp[i] + dp[i - 2]) % MOD
        if i - 3 >= 0:
            dp[i] = (dp[i] + dp[i - 3]) % MOD
            
    print(dp[n] % MOD)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。