AtCoder Beginner Contest 211の参加記録です。
前回の記事にでも書きましたが、競プロ典型90問のおかげで随分と解ける問題が増えました。
今はこのコンテストの★4までの問題を理解しつつ進めていっています。
残りのキーワードは、二次元累積和、バックトラック、拡張ダイクストラ、耳DPです。
この記事は、Python3でABCに参加している茶色レートの私が、私が理解した内容で記載していくブログです。
A – Blood Pressure
血圧を測る問題。
標準入出力と四則演算が書けるかが問われる問題。
標準入出力には、input()
を利用します。Python3で1行に複数の変数を受け取るときには map()
を利用するのが良いと思います。
あとは、(計算順序も含む)四則演算をプログラムできればOKですね。
# AtCoder Beginner Contest 211
# A - Blood Pressure
A,B=map(int,input().split())
C=((A-B)/3+B)
print(C)
B – Cycle Hit
いろいろな解法があると思いますが、私は、set を利用して、種類数を判定する問題として解きました。
入力の制約から、”H”, “2B”, “3B”, “HR” のいずれかしか入力されないため、setにすべてを格納し、setの長さが4であれば”Yes”を出力するコードでACしました。
# AtCoder Beginner Contest 211
# B - Cycle Hit
s1=input()
s2=input()
s3=input()
s4=input()
s=set([s1,s2,s3,s4])
if len(s)==4:
print("Yes")
else:
print("No")
この他にも、望む形のリストと、入力をソートしたリストを比較して、同じであれば”Yes”を出力するコードでもOKですね。
s1=input()
s2=input()
s3=input()
s4=input()
list_input=[s1,s2,s3,s4]
list_input.sort()
list_desire=["H","2B","3B","HR"]
list_desire.sort()
if list_input==list_desire:
print("Yes")
else:
print("No")
ほかにも、ABCのB問題で出てくる繰り返し処理と、条件分岐で解くには、それぞれの文字列が出現したかのフラグを管理して、すべてのフラグがTrueの場合は、”Yes”を出力するようなのでもOKですね。
flg_H=False
flg_2B=False
flg_3B=False
flg_HR=False
for _ in range (4):
s=input()
if s=="H":
flg_H=True
if s=="2B":
flg_2B=True
if s=="3B":
flg_3B=True
if s=="HR":
flg_HR=True
if flg_H==True and flg_2B==True and flg_3B==True and flg_HR==True:
print("Yes")
else:
print("No")
C – chokudai
耳DPの問題。
この記事の冒頭、典型問題で、今から履修する予定の内容に、耳DPがあることを書きましたね。
まさか今日、ここで、C問題で出てくるとは。。。
解けませんでした。
競プロ典型90問の 008 – AtCounter(★4)の問題設定とほぼ同じ問題で、まだ理解していないけれども、この問題のACコードを拾ってきて、少し変えたらAC出来るかな。と思ってやってみましたが、サンプルが合いませんでした。
(コンテスト後に、ループの回数を変更したら理解していませんが、ACしました。)
公式の解説や、他サイトの解説等を見て、ようやく、自分なりに理解できました。
動的計画法で解くとして、状態定義を
dp[ i ][ j ] = Sの j 文字目までを見たときに、”chokudai”の i 文字目までに下線を引く場合の数。
まず、i==0 の時、つまり、下線が引かれない状態は、1通りです。
次に、j==0 の時、つまり、Sから0文字目の長さの時は、0通りです。
そこから、”chokudai”の i 番目の文字とSの j 番目の文字が一致していた場合は、
“chokudai”の i-1 番目まででSの j-1番目までに下線を引いた場合の数と、”chokudai”の i番目と、Sの j-1番目までで出来ていた場合の数とを足し合わせた数になります。
あとは、問題文にある通り、1,000,000,007で割った余りを都度計算していき、最終的には、
dp[len(“chokudai”)][len(S)]を出力すればOKです。
# AtCoder Beginner Contest 211
# C - chokudai
S = input()
N = len(S)
MOD = 10 ** 9 + 7
pattern = 'chokudai'
dp = [ [0 for i in range (N+1) ] for j in range (len(pattern)+1) ]
for i in range(N+1) :
dp[0][i] = 1
for i in range (1,len(pattern)+1) :
for j in range (1,N+1) :
if pattern[i-1] == S[j-1] : # プログラム上の文字位置判定は0-index
dp[i][j] = dp[i][j-1] + dp[i-1][j-1]
dp[i][j] = dp[i][j] % MOD
else :
dp[i][j] = dp[i][j-1]
print(dp[len(pattern)][N])
コメント