ABC129 C - Typical Stairs 解説

はじめに

Pythonで実装しました．そんなところで差が出るなんて，，，という学びがあったので記事にします．

問題

ABC123 C - Typical Stairs

考え方

いわゆるDPの基本的な問題なのだとおもいます．フィボナッチ数列と同じです．

1歩または2歩進めるとうことは，Ｎ段目に到達する方法はN-1段目から来る，またはN-2段目から来るの2通りです．したがってdp[N]をN段目に到達する方法とすれば，

dp[N] = dp[N-1] + dp[N-2]

と表すことができ，これはフィボナッチ数列の一般項と同じです．ここに壊れている床は使えないという条件を加えてやればACとなります．

TLEした実装

mod = 1e+9+7
 
# 入力の受け取り
N, M = map(int,input().split())
#壊れて使えない床をリストAに格納
A = [int(input()) for _ in range(M)]
 
dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1 if 1 not in A else 0
#DP遷移を計算
for i in range(2,N+1):
　#i段目が使えない床の場合はdp[i]=0とする
    if i in A:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1] + dp[i-2])%mod
    
print(int(dp[N]))

ACした実装

mod = 1e+9+7

N, M = map(int,input().split())

#壊れた床の格納方法を変更
#床iが使えるときはA[i]=True
#床iが使えないときはA[i]=False
A = [ True for _ in range(N+1)]
for i in range(M):
    A[int(input())] = False

dp = [0 for _ in range(N+1)]
dp[0] = 1
dp[1] = 1 if A[1] == True else 0
for i in range(2,N+1):
    #dpを計算するときのifの条件式もAに合わせて変更
    if A[i]: dp[i] = (dp[i-1] + dp[i-2])%mod
   
print(int(dp[N]))

これでTLEが解消されてACとなりました．

大学入試

1歩で1段または2段のいずれかで階段を昇るとき，1歩で2段昇ることは連続しないものとする．15段の階段を昇る昇り方は何通りあるか．（07 京都大　文 ）

競プロが大学入試にも役立つ好例ですね！！中高生も胸をはって競プロにいそしみましょう！