【ABC129】AtCoder Beginner Contest 129 A,C問題解答【Python】

A問題 Airplane
C問題
その他

A問題 Airplane

list = list(map(int, input().split()))
list_2 = sorted(list)
print(list_2[0]+list_2[1])

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配列を埋めることで調べる

解答

コード・コメント

#入力
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()

#入力

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()

コード

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()

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問は今回の問題に近いと思います。

A – Frog 1 (atcoder.jp)

B – Frog 2 (atcoder.jp)

その他

他の解説記事一覧

AtCoder Beginner Contest 解答・解説記事一覧