ABC188参戦記

正月気分も抜けて、2021年が本格的に始まりだしましたね。
私はなかなか落ち着いてプログラミング、数学の学習時間がとれない日々が続いています。

先週のABCではB問題が解けなくて涙目になっていましたが、今回のABC188はどこで躓くでしょうか。
C問題が解けるか解けないか、毎回ドキドキしながらコンテスト受けています。

この記事は、茶色下位の私が、自分の理解を書いていきます。使用言語はPython3です。

A – Three-Point Shot

標準入出力と整数の差によって条件分岐のプログラムが書けるかを問われる問題。

標準入力はmapを使用するのが良いと思います。

1行に2変数がある入力の受け取りが難しいとずっと思っていたのですが、practicecontestにPython3でmapを利用した入力の受け取り方法が書いていました。

問題文に書いてある内容を場合分けして、4通りの場合を考えて書くと、このような感じになります。

3点加算しても同点の場合は”No”を出力しないとWAになります。
サンプル3で書いてあるので親切です。
ちゃんとサンプルは確認しましょう。

# AtCoder Beginner Contest 188
# A - Three-Point Shot

X,Y=map(int,input().split())

if X<Y:
    if X+3>Y:
        print("Yes")
    else:
        print("No")
else:   # Y>X また、制約より Y==X はない。
    if Y+3>X:
        print("Yes")
    else:
        print("No")

出力するときに、”YES”や”NO”, “yse”や”no”などの大文字や小文字にしてしまうのにも注意しないとWAになります。

もちろん、上記のようなコードでもACしますが、XとYを区別する必要はなく、ポイントが少ないほうに3を加算して、ポイントが多かったほうよりも大きな数字になればよいので、このようなコードでもACします。

X,Y=map(int,input().split())

if min(X,Y)+3>max(X,Y):
    print("Yes")
else:
    print("No")

数値の差については、いろいろと方法があると思います。私は2つの数の絶対値で判定しました。

x,y=map(int,input().split())

if abs(x-y)<3:
    print("Yes")
else:
    print("No")

B – Orthogonality

繰り返し処理のプログラミングが出来るかの問題。

内積という言葉に戸惑う人もいるかもしれませんが、内積の定義自体は問題文に書いてあるので書いてある通りに実装し、判定すればOKです。

コンテスト中に提出したコードです。

# AtCoder Beginner Contest 188
# B - Orthogonality

N=int(input())

A=list(map(int,input().split()))
B=list(map(int,input().split()))
ans=0
for i in range (N):
    ans+=A[i]*B[i]

if ans==0:
    print("Yes")
else:
    print("No")

もちろん上記のコードでもACするのですが、numpyの扱いに慣れていると、このようなコードになるのかなと予想しています。

内積を求めるのにnumpyのdotメソッドを使用しています。

import numpy as np

N=int(input())

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

a=np.array(A)
b=np.array(B)

if np.dot(a,b)==0:
    print("Yes")
else:
    print("No")

C – ABC Tournament

公式の解説にもある通り、この問題も複数の解法があるようです。
私は、再起関数を作成して解きました。

各プレイヤーを、番号と、強さをセットにした配列で表現します。
参加者の配列を作成し、各プレイヤーを入れていきます。

この参加者の配列を再起関数に投入します。

再起関数のベースケースは、決勝(参加者の数が2の場合)は、強さの低いプレイヤーの番号を返します。
あとは、ベースケースに向かうように関数を書いていきます。

何をするかというと、各対戦の勝者をリストで保持しておき、そのレベルの対戦がすべて終わったら、次のレベルの対戦に進めていきます。

例えば8名の場合は、準々決勝では8名のうち、勝者の4名をリストにして、再起関数を呼び出します。準決勝では4名のうち、勝者の2名をリストにして、再度、再起関数を呼び出します。決勝ではベースケースが実行されて、敗者の番号が返されるといった具合です。

# AtCoder Beginner Contest 188
# C - ABC Tournament

def tournament(players):
    # 次の対戦に上がる参加者をリストで保持する。
    winners=[]

    # basecase
    if len(players)==2:
        if players[0][1]>players[1][1]:
            return players[1][0]
        else:
            return players[0][0]

    # else:
    # 対戦する各2名のうち、勝者をwinner配列に追加する。
    for i in range (len(players)//2):
        if players[i*2][1]>players[(i*2)+1][1]:
            winners.append([players[i*2][0],players[i*2][1]])
        else:
            winners.append([players[(i*2)+1][0],players[(i*2)+1][1]])
    
    return tournament(winners)


N=int(input())
A=list(map(int,input().split()))

ls=[]
# 参加者を[参加番号,強さ]の配列にして、リストに追加する。
for i in range (2**N):
    ls.append([i+1,A[i]])

ans=tournament(ls)

print(ans)

再起関数を使用しないでも、dequeを使用した繰り返し処理や、トーナメント参加者の前半分の勝者と後ろ半分の勝者を比較する。という解法もあるようです。

今回のコンテスト中に、バグらせることなく再起関数が実装できたので、以前の自分よりも進歩している気がします。