見出し画像

AtCoder Beginner Contest 181を見返す

全体

開始30分でA,B問題に正解できたんですが、C問題でWAが1つ出てしまいACできないまま時間切れになりました。AtCoder Problemsをみると今回はC問題灰色、D問題茶色なんですね。問題を見ることも出来ていないですがD問題もどこかで挑戦したいです。

今回はC問題を見直します。

C - Collinearity

問題

3個以上100個未満の座標が与えられるので、同一直線上に3点が並ぶ場合は「Yes」、並ばない場合は「No」を出力する問題

後日作成したコード

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
ans = "No"
for i in range(n):
   x1, y1 = xy[i][0], xy[i][1]
   for j in range(i+1, n):
       x2, y2 = xy[j][0], xy[j][1]
       if x1 == x2 or y1 == y2: k1 = 0
       else: 
           k1 = (y2-y1)/(x2-x1)
       for k in range(j+1, n):
           x3, y3 = xy[k][0], xy[k][1]
           if x1 == x2 == x3 or y1 == y2 == y3: ans = "Yes"
           if x1 == x3 or y1 == y3: continue
           k2 = (y3-y1)/(x3-x1)
           if k1 == k2: ans = "Yes"
           if ans == "Yes": break
       if ans == "Yes": break
   if ans == "Yes": break
print(ans)

与えられる座標の数が最大でも100、よって組み合わせの数は最大でも100c3=161,700です。計算量は10^6程度まで許されているので、この問題は全検索で解答します。

点A, B, Cがある場合、点A,Bを通る直線ABと,点A,Cを通る直線ACの傾きが同じであれば3点が同一直線上にあると言えます。傾きを求めるのは以下の様に行います。

傾き = (yの増加量)/(xの増加量)
なので、A(x1, y1), B(x2, y2)の場合
直線ABの傾き = (y2-y1)/(x2-x1)

上記のコードでは直線ACの場合も同様に傾きを求め、ABの傾きと同値であれば「Yes」を出力する様にしています。X軸やY軸に並行な直線の場合は0除算エラーが出るため、傾きに0を代入する様にしています。

コンテスト中のWAは直線がx軸と並行な場合が考慮漏れしていたために起こっていました。Y軸並行はサンプルにあったので思い付いたんですが、X軸並行の場合は思いつけなかったです、Y軸とX軸はペアで考えてX軸並行の処理も思いつける様になりたい。。。。

この記事が気に入ったらサポートをしてみませんか?