ABC190参戦記

忙しい日々が続き、先週のABC189の振り返りを含めて全く精進出来ない1週間でした。
精進もなにも、今週は1行もコードを書いていません。

そんな状態で臨むABC190ですが、今回もドキドキです。今回もC問題解けなかったらどうしよう。そろそろ安定してC問題解けるようになりたいです。

このブログ記事は、ABCのC問題が解けるか解けないか位の趣味で競技プログラミングを続けている私がABCのC問題までを私が理解できるように書いています。
使用言語はPython3です。

A – Very Very Primitive Game

場合分けをしっかり考えられて、条件分岐を書けるかが問われる問題。

A問題の中では難問だったと思います。

条件分岐は2つ。
・先攻はどちらか。
・アメを多く持っているのはどちらか。

これらの条件分岐を書いていけばOKです。

# AtCoder Beginner Contest 190
# A - Very Very Primitive Game

A,B,C=map(int,input().split())

if C==0:
    if A>B:
        print("Takahashi")
    else:
        print("Aoki")
else:
    if B>A:
        print("Aoki")
    else:
        print("Takahashi")

他にも、後攻の場合は先攻の場合よりも1個多い状態でスタートすると考えたり、

A,B,C=map(int,input().split())

if C==0:
    if A>B:
        print("Takahashi")
    else:
        print("Aoki")
else:
    if A+1>B:
        print("Takahashi")
    else:
        print("Aoki")

先攻と後攻が 0 か 1 で提示されているので、条件分岐にCを組み込んだりして考えてもOKです。

A,B,C=map(int,input().split())

if A+C>B:
    print("Takahashi")
else:
    print("Aoki")

制約からターン数が少ないことがわかるので、for文でシミュレーションしてもOKですね。
ただし、条件を精査しないとWAになります。
今回のこの記事で書こうと思ってシミュレーションのコード書きましたがWA連発しました。

A,B,C=map(int,input().split())

A+=C

for i in range (100):
    if i==0 and B==0 and A>0:
        print("Takahashi")
        exit()
    A-=1
    if A<=0:
        print("Aoki")
        exit()
    B-=1
    if B<=0:
        print("Takahashi")
        exit()

B – Magic 3

繰り返し処理のfor文と条件分岐が適切に書けるかの問題。

問題文中には、NGの条件が書かれているので、NGの条件の場合は繰り返し処理を進めていって、OKの条件の場合に”Yes”を出力してプログラムを終わらせる。もしも繰り返し処理すべてが終わった時点でプログラムが終わっていなければ”No”を出力すればOKです。

# AtCoder Beginner Contest 190
# B - Magic 3

N,S,D=map(int,input().split())

for _ in range (N):
    X,Y=map(int,input().split())
    if X>=S:
        continue
    if Y>D:
        print("Yes")
        exit()
    else:
        continue

print("No")

C – Bowls and Dishes

bit全探索ができるかを問われる問題。

私は今回もC問題解けませんでした。
bit全探索が一瞬頭をよぎりましたが、問題が最近行われた ARC111-B B – Reversible Cards に似てるな。と思って、このARC111-Bの解法を調べて時間を溶かしました。そして、結局解けませんでした。

以下の手順を記述していけばOKです。
・各値を受け取る。(0-indexにしておく)
・プレイヤーの選択肢を全探索する。(bit全探索)
・探索の中で、皿にボールが載っている状態を配列で表す。
・条件を判定していき、条件に合う件数をカウントする。
・最大値の場合は最大値を更新する。
・答えを出力する。

bit全探索は以下のようなコードで表されます。

N=3

for i in range(2**N):
    P=[]    
    for j in range(N):
        if i>>j & 1 ==1:
            P.append(1)
        else:
            P.append(0)
    print(P)

# >>
'''
[0, 0, 0]
[1, 0, 0]
[0, 1, 0]
[1, 1, 0]
[0, 0, 1]
[1, 0, 1]
[0, 1, 1]
[1, 1, 1]
'''

あとはbit全探索で表される数字の「0」はCの番号の皿に、「1」はDの番号の皿にボールを載せると考えれば皿の配列が出来上がるので、その状態で条件を確認していけばOKです。

# AtCoder Beginner Contest 190
# C - Bowls and Dishes

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

conditions=[]
for _ in range (M):
    a,b=map(int,input().split())
    conditions.append([a-1,b-1])

K=int(input())

playerselect=[]
for _ in range (K):
    c,d=map(int,input().split())
    playerselect.append((c-1,d-1))

ans=0

# bit全探索
for ptn in range(2**K):
    selection=[]
    dishes=[0]*N

    for player in range(K):
        if ptn>>player & 1 ==1:
            selection.append(1)
        else:
            selection.append(0)
    # print(selection)

    for select_i in range (K):
        Chosen_dish=playerselect[select_i][selection[select_i]]
        dishes[Chosen_dish] +=1
    
    tempans=0

    for condition_i in range (M):
        if dishes[conditions[condition_i][0]]>0 and dishes[conditions[condition_i][1]]>0:
            tempans+=1

    ans=max(ans,tempans)


print(ans)

今回のC問題は制約が少ないことからbit全探索が頭をよぎったのですが、落ち着いて考えられませんでした。
コンテスト中は焦ってしまうのを直したいですね。