壊れた段をよけて階段を上る方法の数

動的計画法
問題 15
やや難しい
目安 45 分

1 段、2 段、3 段ずつ上れる階段で、壊れた段を踏まずに上までたどり着く上り方の数を求める。前の段の答えを使って次の段の答えを作る、動的計画法の練習です。

本番の試験は PC で受けることが多いので、PC での練習をすすめます。スマホでも、読んで、書いて、採点するところまで動きます。

入力は標準入力から読み、答えは標準出力に書きます。1 テストあたり 3 秒までです。

問題

工場の点検で、N 段の非常階段を上ります。地面を 0 段目、いちばん上を N 段目とします。1 回の動きで、1 段、2 段、3 段のどれかだけ上ることができます。ただし、途中の M 個の段は壊れていて、踏むことができません。

0 段目から N 段目までちょうどたどり着く上り方は、何通りあるでしょうか。動きの順番が違えば、別の上り方として数えます。答えはとても大きくなることがあるので、1000000007 (10^9 + 7) で割った余りを出力してください。上り方が 1 つもないときは 0 を出力します。

入力の形式

N M
b_1
b_2
...
b_M

1 行目に段の数 N と壊れた段の数 M が半角の空白 1 つで区切られて並びます。続く M 行に、壊れた段の番号 b_i が 1 行に 1 つずつ、小さい順に並びます。M が 0 のときは、1 行目だけです。

出力の形式

上り方の数を 1000000007 で割った余りを 1 行で出力します。

制約

N は 1 以上 1000000 以下の整数です
M は 0 以上 100000 以下で、N - 1 以下の整数です
b_i は 1 以上 N - 1 以下の整数で、b_1 < b_2 < ... < b_M を満たします (地面と、いちばん上の段は壊れていません)

入力と出力の例

例 1

5 段の階段で、3 段目が壊れています。上り方は (1, 1, 2, 1)、(1, 1, 3)、(2, 2, 1)、(1, 3, 1)、(2, 3) の 5 通りです。たとえば (1, 2, 2) は 3 段目を踏むので数えません。

入力

5 1
3

出力

例 2

4 段の階段で、壊れた段はありません。上り方は 7 通りです。

入力

4 0

出力

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

全部のテストに通ると、解答と考え方が開きます。

先にヒントを試すと、自分で解けた手応えが残ります。どうしても詰まったときは、ここから開けます。

解答

ways[i] を「0 段目から i 段目まで、壊れた段を踏まずに上る方法の数」とします。ways[0] は 1 です。i を 1 から N まで順に見て、i が壊れた段なら ways[i] は 0 のままにし、そうでなければ ways[i - 1] と ways[i - 2] と ways[i - 3] (番号が 0 以上のものだけ) を足して、1000000007 で割った余りを入れます。ways[N] が答えです。各段で一定の回数の計算をするだけなので、全部で O(N + M) です。

Python

import sys

MOD = 10**9 + 7

data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
broken = [False] * (n + 1)
for i in range(m):
    broken[int(data[2 + i])] = True

ways = [0] * (n + 1)
ways[0] = 1
for i in range(1, n + 1):
    if broken[i]:
        continue
    total = ways[i - 1]
    if i >= 2:
        total += ways[i - 2]
    if i >= 3:
        total += ways[i - 3]
    ways[i] = total % MOD

print(ways[n])

JavaScript

const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);
const MOD = 1000000007;
const n = data[0];
const m = data[1];
const broken = new Array(n + 1).fill(false);
for (let i = 0; i < m; i++) broken[data[2 + i]] = true;

const ways = new Array(n + 1).fill(0);
ways[0] = 1;
for (let i = 1; i <= n; i++) {
  if (broken[i]) continue;
  let total = ways[i - 1];
  if (i >= 2) total += ways[i - 2];
  if (i >= 3) total += ways[i - 3];
  ways[i] = total % MOD;
}

console.log(ways[n]);

計算量

時間は O(N + M) です。壊れた段の印を付けるのに O(M)、表を下から埋めるのに O(N) かかります。

遅い解き方は、表を使わずに、上り方を 1 つずつ全部たどって数えるものです (記憶なしの再帰と同じ数え方)。数える量は上り方の数そのものなので、N が 1 増えるごとに約 1.8 倍に増えます。N が 20 なら 12 万通りほどで終わりますが、N が 100 万では終わりません。再帰で書いた場合は、深さが N になって止まってしまうこともあります。

よくある間違い

最後に 1 回だけ 1000000007 で割る。Python では答えは合いますが、途中の数が何十万桁にもなって足し算が遅くなります。JavaScript では数が大きすぎて正しい値を表せません。足すたびに割った余りにします
ways[0] を 0 にしてしまい、全部が 0 になる。地面に立っている状態は 1 通りと数えます
壊れた段を「その段から先へ進めない」だけにして、その段までの数を 0 にし忘れる
i が 1 や 2 のときに ways[i - 3] を読み、Python では負の番号が配列の後ろを指して、間違った値を足してしまう
壊れた段の番号を、ずっと list のまま「in」で調べる。毎回 O(M) かかるので、N 段ぶんでは遅くなります。印の配列か set にします

解答を動かした版 Python 3.12.14Node.js 22.23.4確認日 2026/10/31

main.py

import sys

MOD = 10**9 + 7

data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
broken_steps = [int(data[2 + i]) for i in range(m)]

# ここから書く

入力

5 1
3

出力

「実行する」を押すと、ここに出力が出ます

できているか「提出して採点」を押すと、隠れたテストを全部走らせて、通ったかをここに出します