ABC211参戦記

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