Submission #68670872

---

Source Code Expand

#include <iostream>
#include <vector>

int main() {

    int mod = 1e9 + 7; // 10^9 + 7

    // 入力
    int stairs, broken_stairs;
    std::cin >> stairs >> broken_stairs;

    // 破損した段を格納するベクタ
    std::vector<int> is_broken(stairs + 1, 0);

    // 破損した段を入力
    for (int i = 0; i < broken_stairs; ++i) {
        int broken_step;
        std::cin >> broken_step;

        is_broken[broken_step] = 1;
    }

    /*
    動的計画法について

    動的計画法とは、問題を小さな問題に分解し、それらの答えを組み合わせて全体の答えを求める手法のことである。この問題では、それぞれの段に到達する方法の数を部分的に計算し、それらを組み合わせて最終的な答えを求めている。


    i段目に到達する方法の数をdp(i)とすると、求める式は以下のようになる。

    1. 0段目に行く方法は1通りである。(最初から立っているので)
    dp(0) = 1

    2. 1段目に行く方法は、1段前から上がる方法しかない。よって同様に1通りである。
    dp(1) = 1

    3. 2段目以降は、1段前から上がる方法と、2段前から上がる方法が使える。よって、1段前にたどり着く方法の数と、2段前にたどり着く方法の数の和に等しい。
    dp(i) = dp(i - 1) + dp(i - 2) (i ≧ 2)

    これらの式を用いて、N段目に到達する方法の数を計算していくことができる。

    なお、破損した段は到達できないため、その段に対しては処理をスキップする必要がある。
    */

    // i段目に到達する方法の数を格納するベクタ
    std::vector<int> dp(stairs + 1, 0);

    // 1. 0段目に行く方法は1通り
    dp[0] = 1;

    // 2. 1段目に行く方法も1通り
    if(is_broken[1] == 0) { // 破損していない場合
        dp[1] = 1;
    }

    for (int i = 2; i <= stairs; ++i) {
        if(is_broken[i] == 0) {  // 破損していない場合
            // 3. 2段目以降は、1段前から上がる方法と、2段前から上がる方法が使える。
            // 注意: 値が非常に大きくなる可能性があるので、この時点でmodで割った余りを使うこと。
            dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
        }
    }

    // 最上段に到達する方法の数を出力
    std::cout << dp[stairs] << std::endl;

    return 0;
}

Submission Info

Judge Result