abc129cのノート

abc129c

階段飛ばしの問題。

先輩に「配るdp」での解き方を教わった。

atcoder.jp

いい感じに理解できたので、それを残す。

配るdpについて

本問題において配るdpは「その配列要素に辿りつくまでに何通りがあるか」を保存し、それを利用する。

問題中で高橋君は1または2段飛ばしの動きをする。これをもとに穴なしで2段目にたどり着く通り数を考えると、

「最初の場所(0段目)のi通りから2段飛ばし」による1通りと、

「1段目から、1段上がる」操作による1通り

の合計2通りがある。

3段目も同様に穴なしで考えると1段目からの2段飛ばしと、2段目からの1段上がる2通りである。

通り数を保存すると、この問題だと「今のindexの2つ前の要素の和」で次の要素の通り数が決まる。

ただし、穴についてはこの処理を行わないことによって整合性をもたせることができる。

3段穴なしで考えると、0段目も含めるので

[1,1,1,1]

の配列を用意して2からforを回す。(2からでないと参照ができないし、indexの0,1に関しては一通りしかないので1,1のままで良いから)

index 2を考えると前2要素の和なので2となる。

index 3を考えると同様に3となる。

したがって、[1,1,2,3]の配列に変形される。

基本的にはこれを続けていくことで求めたいもの-1のindexまで求められる。

書いたコード

n,m = map(int,input().split())
l = [1]*(n+1)
# This is [Kubaru_dp]

for i in range(m):
    a = int(input())
    l[a] = 0

for i in range(2,n+1):
    if l[i]==0:
        continue
    l[i] = (l[i-1]+l[i-2])%(10**9+7)
else:
    print(l[-1])

基本的入力は省略する。
l(エル)について一つ多く配列を取っているが、答えを簡単に出力したいためにこのようにした。単純にnまで出力したいがn個だとindexが0~(n-1)までしか出ないからである。

一度目の入力を受け取るfor文内でl[a] = 0がありこれは穴である。

二度目のforで配るdpの操作をしている。lが0であったら、今穴の上に高橋くんがいることを仮定しているのでこれは捨てるべき操作になる。したがってこれを無視する。
なんとなくここで、値が足りなくなる気がするが、穴を飛び越える時点で穴を通る通りが0通りであることを考えるとわかりやすいかもしれない。
また、0が二回くる時にここで途切れ以降が0埋めされる。したがって答えが0の際もちゃんと出力される。

lの要素の更新だが、制約どおり(10**9+7)で出力するので更新時点でこれを行う。確かフェルマーの小定理。