A問題 Airplane
|
1 2 3 |
list = list(map(int, input().split())) list_2 = sorted(list) print(list_2[0]+list_2[1]) |
C問題
方針
・dp[n]：n段目までの階段の登り方の数とする
・dp[n]を求めるための遷移式：dp[n]=dp[n-1]+dp[n-2]
・壊れている階段を配列で管理し、壊れていない場合のみ登り方の数を計算する
・壊れている階段への上り方の数は0、壊れていない階段への上り方の数はDP配列を埋めることで調べる
解答
コード・コメント
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#入力 n,m = map(int, input().split()) #modを設定 mod = 1000000007 #階段の状態を管理する配列。Trueなら正常、Falseなら壊れている状態とする #1-indexにするためn+1個の要素で作成 stairs = [True]*(n+1) #mは壊れている階段の数 for i in range(m): #入力 a = int(input()) #Falseで壊れている状態を示す stairs[a]=False #DP配列を作成。各要素は何段目の階段であるかを示す #1-indexにするためn+1個の要素で作成 dp = [0]*(n+1) #まだ階段を登っていない状態(地上) dp[0]=0 #1段目が壊れていない場合 if stairs[1]: #登り方は1通り dp[1]=1 #階段が1段しかなく、1段目が壊れている場合 if n==1 and not(stairs[1]): #登る階段がないため0を出力 print(0) #終了 exit() #階段が1段しかなく、1段目が正常な場合 if n==1: #1を出力 print(1) #終了 exit() #2段目が正常な場合 if stairs[2]: #1段目が正常な場合 if dp[1]==1: #2段目までの登り方は2通り dp[2]=2 #1段目が壊れている場合 else: #2段目までの登り方は1通り dp[2]=1 #3段目以降の階段の登り方の数を調べる for i in range(3,n+1): #i段目の階段が正常な場合 if stairs[i] is True: #i-1段目までの登り方とi-2段目までの登り方の合計がi段目までの登り方の数になる #modで割り、その余りを取ることで数字が大きくなることを防ぐ dp[i] = (dp[i-1] + dp[i-2])%mod #階段の状態を表す配列を逆順に並べ替える stairs=stairs[::-1] #DP配列を逆順に並べ替える dp=dp[::-1] #逆順に並べ替えた階段の状態を順に調べ、初めて壊れていない階段に当たった場合にそこまでの登り方の数を出力する #(最上段の階段が壊れている場合はその次の階段までの登り方を出力 for i in range(len(stairs)): #階段が正常な場合 if stairs[i]: #modで割り、その余りを解答とする ans = dp[i]%mod #解答を出力 print(ans) #終了 exit() |
コード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
n,m = map(int, input().split()) mod = 1000000007 stairs = [True]*(n+1) for i in range(m): a = int(input()) stairs[a]=False dp = [0]*(n+1) dp[0]=0 if stairs[1]: dp[1]=1 if n==1 and not(stairs[1]): print(0) exit() if n==1: print(1) exit() if stairs[2]: if dp[1]==1: dp[2]=2 else: dp[2]=1 for i in range(3,n+1): if stairs[i] is True: dp[i] = (dp[i-1] + dp[i-2])%mod stairs=stairs[::-1] dp=dp[::-1] for i in range(len(stairs)): if stairs[i]: ans = dp[i]%mod print(ans) exit() |
参考
mod(合同式)
一番わかりやすいです。
【高校数学(発展)】合同式①(modとは何か)【整数】 – YouTube
書籍で学ぶならこちら。
動的計画法(DP)
Atcoderには動的計画法(DP)を集めた問題集があるのですが、最初の2問は今回の問題に近いと思います。
その他
他の解説記事一覧
コメント