ABC 129惨敗

♯ABC 129惨敗
Atcoder始めて3日目。案の定、Cも解けない惨敗。組み合わせがどうなるか思いつかなかった。
なので、解けなかった問題をやる。

C Typical Stairs

壊れてない連続する階段の組み合わせ数の掛け算で出来るのは分かったが、組み合わせ数が分からないという。
改造フィボナッチで出来るらしいが、思いついたのは壊れている前後で分離して掛ける方式であった。

連続する階段数をxとすると組み合わせ数yは
$y=f(x)=fib(x+1)$
である。
壊れている階段aiなら、(ai-1)-posが連続段数xとなり、後は掛け算するだけでよかった。
ただし、1段目とN-1段目が壊れているとき、長さ0になるので、長さから直接計算しようとして0のことを忘れているとバグってREになる。
コードはオフセットすべきなのを無理矢理動くようにしたので、後で修正する。

でも改造フィボナッチの方が簡単だと思った。

qiita.py

def mulmod(x,y,p):
    return x*y % p

def test(n):
    if n<1:
        return 1
    memo = [0]*(n+1)
    memo[0] = 1
    memo[1] = 1
    for i in range(2,n+1):
        memo[i] = (memo[i-1] + memo[i-2])%1000000007
    return memo[n]

n,m = map(int,input().split())
a =[]
pos = 0
result = 1
last = -1
for i in range(m):
    x = int(input())
    if (last+1) == x:
        print(0)
        exit(0)
    last = x
    a.append(x)

for i in a:
    result = mulmod(test(i-pos-1),result,1000000007)
    pos = i+1

result = mulmod(test(n-pos),result,1000000007)
print(result)

反省点

数学的知識の欠如。フィボナッチなんて頭の片隅にもなかった。
過去のC問題を見ると問題文の日本語が理解出来ない。
パズルと同じで慣れないとうまくいかないから、過去問をやってどんな問題文の傾向とかを理解する必要があった。