🔖

ABC129 C - Typical Stairsのメモ

2023/01/06に公開

AtCoder

競プロ

tech

目についたC問題を解いてみるの回です。これはABC初参加の回で、当時は解けませんでした。

考察

愚直にやろうとすると、階段を1歩上がった場合と2歩上がったとで分岐して、さらにそれから1歩上がった場合、2歩上がった場合、と組み合わせ爆発が起こることが想像できます。

これは以前似たような問題を解いたことがあったので、DPで解けると直感しました。

もう少し詳細に考えます。一旦壊れている位置のことは考えないこととすると、1段目に行く方法は0段目から1段上がる方法の1通りのみです。2段目に行く方法は、0段目から1段ずつ上がる方法と一気に2段上がる方法の2通りあります。
じゃあ3段目は？これは1段目から1段ずつ上がる方法、1段目に行ってから2段上がる方法、一気に2段目に行ってから1段上がる方法の3通りです。
このように0段目から行く方法を考えるとややこしいのですが、これは実は分解して考えることができます。
3段目に行く方法として

1段目から1段ずつ上がる方法
1段目に行ってから2段上がる方法
一気に2段目に行ってから1段上がる方法

がありますが、これは遷移する段で考えるとそれぞれ

0 -> 1 -> 2 -> 3
0 -> 1 -> 3
0 -> 2 -> 3

となります。注目いただきたいのは最後の部分で、要するに3段目に行くには「1段目から2段上がって行く方法」と「2段目から1段上がっていく方法」の2つしかないということです。ではなぜ3通りあるのかというと、そもそも2段目に行く方法が2通りあるからです。

つまり、3段目に行く方法が何通りあるかは、「1段目に行く方法が何通りあるか」と「2段目に行く方法が何通りあるか」を足すことで求められます。

一般化すると、N段目に行く方法が何通りあるかは、「N-2段目に行く方法が何通りあるか」と「N-1段目に行く方法が何通りあるか」を足すことで求められます。

この計算を最初から初めて、壊れている段をスキップしつつNまで繰り返せば答えが求まります。
このアルゴリズムであれば計算量は $O(N)$ なので十分間に合います。
また、このアルゴリズムがDPそのものです。

つまり、DP表では上った数が位置で、その位置に到達可能なパターン数を値として埋めます。
上記はいわゆる貰うDPの発想です。ある位置に注目している時、その位置に到達可能な方法は1つ前から来る場合と2つ前から来る場合の2つなので、その位置から値をもらって足した値を埋めればいいです。

壊れている位置に到達することは不可能なので、埋めません。

あとは、答えが巨大になる可能性があるので都度あまりをとります。

実装

最初は0段目にいるので、それを表現可能なようにDP表はN+1の大きさを確保します。
0段目に行く方法は、初期位置ということで1通りなのでそれで埋めます。これが計算の起点となります。
それ以外は0で初期化します。

fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val a = List(m) {
        readLine()!!.toInt()
    }.toSet()

    val mod = 1000000007

    val dp = IntArray(n+1)
    dp[0] = 1

    for(i in 1..n) {
        if(i in a) {
            continue
        }

        if(i > 1) {
            dp[i] = dp[i-2] % mod
        }

        dp[i] += dp[i-1] % mod
        dp[i] %= mod
    }
    println(dp[n] % mod)
}

壊れている段は埋めないようにスキップします。
また、1段目にいる場合だけは2段前から遷移ができないのでそれはスキップします。
ここは、先にループの外で埋めてしまってもよかったかもしれません。
（ただし、その場合は1が壊れている段でないかどうかは判定が必要）

あとは2段前と1段前の値を貰って足し合わせるだけです。貰う元が壊れている段だったとしても、0を貰うだけなので計算上は問題ありません。

あとはあまりを随時とってdp[n]を出力して終わりです。

あまりをとるのはちょっと苦手で、無駄にとっている箇所があるかもしれません。まあ、無駄にとっても結果はかわらないはずなのでとりあえず入れています。

感想

1次元とはいえDPについて知っている必要があるのと、随時あまりをとるという考え方も知っている必要があるので、リアルタイムで参加していた当時の私は解けるはずのない問題でした。

しかし今やったら簡単だったので、多少は成長を実感できてよかったです。

（執筆時間：15分10秒 + 修正時間16分57秒）

考察

実装

感想

Discussion