ABC181参戦記

1週間間が空いてABC(AtCoderBigennersContest)が開催されました。

先週はARC(AtCoderRegularContest)106が、昨日はARC107が開催されていました。

ARCはABCの初級者クラスではなく、中級者クラスなので、解けない問題が多いですが、ARC107とARC108に参加して、ともにA問題が無事解けて、Ratingも上がり、茶色になりました！

土曜日のARCでHighestを更新しましたが、本日のABC181でC問題が解けなければ茶色から灰色に落ちそうなきもします。

毎回ABCのC問題が解けるか解けないかくらいのちょっと前に茶色になった私のABC参戦記チラ裏ブログ。ABC181のAからC問題までの思考過程とPython3のACコードが書かれています。

A – Heavy Rotation

標準入出力と偶奇判定ができるかを問われる問題。

奇数日後は”White”の服を、偶数日後は”Black”の服を着るということがわかれば、ifの条件分岐で次のように書ければOKです。

# AtCoder Beginner Contest 181
# A - Heavy Rotation


N=int(input())

if N%2==0:
    print("White")
else:
    print("Black")

“white”や”WHITE”などと書かないように出力例をしっかりと確認することも重要ですね。

最近はA問題でも1行に複数の入力が入っている問題が多かったですが、今回は1行1変数だったので初心者には親切な入力だった思います。

B – Trapezoid Sum

区間の和を求める問題。
区間の和を求める部分を愚直にfor文を使用するとTLEします。(私はしました。)

1から始まり、nまでの数の和は、

n*(n+1)/2

で求まります。

より一般的な等差数列の和の公式などについて詳しく知りたい方は、こちらのサイトなどで確認できます。

問題のA以上B以下の数の和は1からBまでの和から、１からA未満の和を引いた数になります。

Aを含めるために、1からA未満(A-1)までの数を足すのが注意点ですね。

# AtCoder Beginner Contest 181
# B - Trapezoid Sum


N=int(input())

ans=0

for i in range (N):
    A,B=map(int,input().split())
    a=A*(A-1)//2
    b=B*(B+1)//2
    ans+=b-a

print(ans)

C – Collinearity

N個の中から3つを選ぶ組合わせを問われつつ、
xy平面に一次関数のグラフy=ax+bを描いて、3点A,B,Cで直線ABと直線BCの傾き(a)が一致していることを判定する問題。

今回もC問題解けませんでした。

メモでxの増加量に対するyの増加量とかっていうメモがあって、そのまま突き進めば解けたかもしれないのに、列ベクトルでnumpy使おうとしだして迷走した挙句解けませんでした。

解説見ても3つの内、2つの点を通る直線y=ax+bの傾き(a)は一緒だけれどもx=0の時のyの値(b)が異なる場合はどうなるのだろう？とずっと悩んでいたので、突き進んでも解けなかった可能性があります。
ちなみに、3点の中から2点を結ぶ直線と残った1点と先ほど選んだ2点のうちの1点を結ぶ直線の傾きが一緒でx=0の時の値が異なることはありません。これに気づくのに2時間くらいかかりました。

まずは、3点(A,B,C)のうち、A=[x1,y1]とB=[x2,y2]を使用して、1次関数のグラフy=ax+bを表してみます。
(愚直に書いているのですごく見づらいです。)

    # A,Bを使用して2次方程式を解く
    # b=A[1]-A[0]a
    # b=B[1]-B[0]a
    # //bが同じなので、2つの式をつなぐ
    # //その後、移行してaで括る
    # A[1]-A[0]a=B[1]-B[0]a
    # A[1]-B[1]=A[0]a-B[0]a
    # a(A[0]-B[0])=A[1]-B[1]
    # a=(A[1]-B[1])/(A[0]-B[0])

これで、AとBを利用した傾きを計算出来ました。

これと同じことをBとCで実施します。
(上記の最終行のAをBに、BをCに書き換えただけのもの。)

    # aa=(B[1]-C[1])/(B[0]-C[0])

これで、a(AとBの直線の傾き)==aa(BとCの直線の傾き)であれば3点が直線状に存在することになります。

3点が直線かどうかの判定式を以下のように作って試すと、

def areTheseStraight(A,B,C):
    a=(A[1]-B[1])/(A[0]-B[0])
    aa=(B[1]-C[1])/(B[0]-C[0])

    if a==aa:
        return True
    else:
        return False

A=[0,1]
B=[0,2]
C=[0,3]

print(areTheseStraight(A,B,C))
// -> 
ZeroDivisionError: division by zero

ZeroDivisionErrorが出ちゃいました。

割り算は誤差やこのエラーが出るので、ちょっと不格好ですが、次のようにするとエラーもなく通るようになります。

def areTheseStraight(A,B,C):
    # a=(A[1]-B[1])/(A[0]-B[0])
    # aa=(B[1]-C[1])/(B[0]-C[0])

    if (A[1]-B[1])*(B[0]-C[0])==(B[1]-C[1])*(A[0]-B[0]):
        return True
    else:
        return False

A=[0,1]
B=[0,2]
C=[0,3]

print(areTheseStraight(A,B,C))
// -> True

これで3点が直線状に並んでいるかどうかを判定する関数はできました。

あとは、N個の中から3個を選ぶ組み合わせが出来れば行けそうです。

Python3では、itertoolsというライブラリの中のcombinationsモジュールが便利です。

これらを組み合わせて提出すればOKです。

# AtCoder Beginner Contest 181
# C - Collinearity

from itertools import combinations

def areTheseStraight(A,B,C):
    # a=(A[1]-B[1])/(A[0]-B[0])
    # aa=(B[1]-C[1])/(B[0]-C[0])

    if (A[1]-B[1])*(B[0]-C[0])==(B[1]-C[1])*(A[0]-B[0]):
        return True
    else:
        return False


N=int(input())

ls=[]

for i in range (N):
    xy=list(map(int,input().split()))
    ls.append(xy)

Combi=list(combinations(ls,3))

for i in range (len(Combi)):
    A=Combi[i][0]
    B=Combi[i][1]
    C=Combi[i][2]
    judge=areTheseStraight(A,B,C)
    if judge==True:
        print("Yes")
        exit()

print("No")