ABC129 C - Typical Stairs

atcoder.jp

地味にまともなDP解いたのは初かもしれない。 DP典型を逃しまくってるので、まだまだ強化必要だなあ。

• dpの状態数は開始位置を含むN+1とした（遷移先がN段目まである）
• 壊れてる階段の数はMだけど、最大でたかだかN-1なので、-1（存在しない段）のN+1個で雑に初期化
• 壊れてる段は集合にして、存在確認することとした
  • けど、解説にある通り、該当位置が壊れているか、のテーブル持つ方が賢い気もする。今回の制約（壊れてる段はそれぞれユニーク）だと集合でも問題なさそうか・・・
• 遷移は、①1段前から登ってくる＋②2段前から登ってくる　の単に合計。ただし壊れてる段（壊れてる段集合にヒット）の場合は0、とした

def resolve():
  N,M=map(int,input().split())
  A=[-1]*(N+1)
  dp=[0]*(N+1)
  MOD=10**9+7

  if(M!=0):
    for i in range(M):
      A[i]=int(input())

  A=set(A)
  dp[0]=1
  dp[1]=1
  if(1 in A):
    dp[1]=0

  for i in range(2,N+1):
    if(i in A):
      dp[i]=0
    else:
      dp[i]=(dp[i-1]%MOD+dp[i-2]%MOD)%MOD

  print(dp[N])

こんだけで解けてちょっと感動。 実は事前に「2つ破損が続いたら答えは0」みたいな条件たくさん作らんといかんと思っていたけど、dpで全部辻褄あっててキレイ。dpはうつくしい。