AtCoder Beginner Contest 181 A〜C問題

AtCoder Python

前書き

D問題よりA~C問題を高速で解くトレーニングを積みたいと思います。

A問題

atcoder.jp

難易度：灰

n = int(input())
if n %2==0: print('White')
else: print('Black')

B問題

atcoder.jp

難易度：灰色
時間：AとBを合わせて8分

N = int(input())
AB = [list(map(int, input().split())) for i in range(N)]
sum_ = 0
for ab in AB:
  sum_+=((ab[0]+ab[1])*(ab[1]-ab[0]+1)/2)
print(int(sum_))

C問題

難易度：灰色
時間：37分+(TLEペナル5分)

灰色問題の中では難しい方。
「3つの座標点が一直線上に存在する組み合わせ」が存在するかという問題。

3≤N≤10**2だったので、3つの座標店の組み合わせを知りたければだいたい10**6通りのパターンを全探索すればいけるやんと思いました。そこから傾きと切片の値を取得して、3つの座標を結ぶ数直線の一次関数式が一致しているか確認すればいいと思いました。

数学的なイメージとしてはこちら
examist.jp

check()では2座標点間の傾き・切片を取得しています。

場合分けは以下の通りです。

  • x座標と並行
  • y座標と並行（傾き∞、切片なしなのでどちらも暫定的に100000とします）
  • 他

結果

TLE →(Pypy3)で実行するとAC。
Pythonで実行すべきかPypyで実行すべきかを見極めたいですよね。

import itertools
import sys

N = int(input())
XY = [list(map(int, input().split())) for n in range(N)]

xylis = list(list(itertools.permutations(XY, 3)))

def check(xy1, xy2):
  x1, y1 = xy1[0], xy1[1]
  x2, y2 = xy2[0], xy2[1]
  
  if y1==y2:
    return 0,y1
  elif x1==x2:
    return 100000,100000
    sys.exit()
  else:
    a = (y2-y1)/(x2-x1)
    b = a*(-x1)+y1
    return a,b

for j in range(len(xylis)):
  a1,b1 = check(xylis[j][0],xylis[j][1])
  a2,b2 = check(xylis[j][1],xylis[j][2])
  a3,b3 = check(xylis[j][0],xylis[j][2])
  if (a1==a2==a3)and(b1==b2==b3):
    print('Yes')
    sys.exit()
print('No')

反省

もっと賢い方。
qiita.com