AtCoder Beginner Contest (ABC) 181 PythonでC問題解いてみた
前回解いたやつ
こんばんは。めりーです。
寒すぎて朝起きたら喉ががっさがさで頭がだいぶ痛い現象がここ数日多発しております。
「風邪なのかな・・・？」
って思うんですけど、目覚めてベットの上で1時間くらいスマホいじってたら治るのでおそらく風邪ではなさそう。
起きる時間に合わせて暖房予約しておこうかな・・・。
そんなわけで今日も元気にAtCoder Beginner Contest (abc) 181 C問題解いていきます。
今回も解説を見ずに解けたのでステップアップを考えてもいいのかな？
言語はPython、提出はPyPyです。
目次
C問題 Collinearity
問題文
点がN個与えられます。
その中の3点を選んでその3点が同一直線状に存在することはあり得るでしょうか。
という問題。
数学系の問題ですね。
Nの個数が102までという少なめの設定。
なので全探索で間に合いそうですね。
また、条件（1直線状に並ぶか否か）の判別には、傾きが等しくなるかどうかを用いました。
例えば点A,Bの傾きと点A,Cの傾きが等しければ、3点ABCは一直線上にあると言えます。
2直線AB,ACが平行になることはあり得ません。
※点Ａで交わってるので
というわけで、3点のうち2点の傾きを2つ比較して、等しければ条件を満たすと言えます。
数学的に表すと、
(x[1] - x[2]) ÷ (y[1] - y[2]) = (x[2] - x[3]) ÷ (y[2] - y[3])
が成り立てば条件を満たすと言えます。
というわけで、方針としては、
1. 全探索する。
2. 各パターンにおいて、条件を満たすか確認する。
3. 1つでも満たしたら「Yes」、それ以外なら「No」を出力。
という形で行きましょう。
実装したコードはこちら
n = int(input())
x = []
y = []
for _ in range(n):
X,Y = map(int,input().split())
x.append(X)
y.append(Y)
flg = 0
for i in range(n-2):
for j in range(i+1,n-1):
for k in range(j+1,n):
# 傾きが2つ等しいかでチェック
if (x[i]-x[j])*(y[j]-y[k]) == (x[j]-x[k])*(y[i]-y[j]) :
flg = 1
break
if flg:
break
if flg:
break
if flg:
print("Yes")
else:
print("No")
三重ループだけど、計算量は1023 = 106以下なので問題ないですね。
※AtCoderでは、ループが約108くらい回せる(TLEにならないループ数)
解説していきます。
入力部分はいいとして、
for i in range(n-2):
for j in range(i+1,n-1):
for k in range(j+1,n):
# 傾きが2つ等しいかでチェック
if (x[i]-x[j])*(y[j]-y[k]) == (x[j]-x[k])*(y[i]-y[j]) :
flg = 1
break
if flg:
break
if flg:
break
ここがこの問題の山場ですね。
3点を選ぶときに、選び方が重複する(A,B,CとB,C,Aみたいに)と計算量の無駄なので、3点の一番小さいのをi、2番目がj、3番目がkとなるように三重ループを組みました。
なので、3つのループ、範囲がちょっとずつ違います。
iのループでrange(n)にしちゃうと、iがn-1の時、取り得るj,kがなくなってしまうので。
また、iがn-2の時は取り得るkがなくなってしまうので。
そして、傾きが等しいかどうかチェック。
実は、割り算を条件式に入れると、切り捨てなどで誤差が出る場合があるのです。
なので、なるべく割り算を入れないようにしましょう。
なので、条件式を式変形しました。
(x[1] - x[2]) ÷ (y[1] - y[2]) = (x[2] - x[3]) ÷ (y[2] - y[3]) 両辺に(y[1] - y[2]) × (y[2] - y[3])をかける（分母を払う） (x[1] - x[2]) × (y[2] - y[3]) = (x[2] - x[3]) × (y[1] - y[2])
この式の1,2,3にそれぞれi,j,kを当てはめました。
そして、この条件式を満たした場合、flgを更新して、breakでループを抜けます。
if flg:
print("Yes")
else:
print("No")
そして最後、flg = 1の場合(条件を満たした場合)は「Yes」、
flg = 0の場合(条件を満たしていない場合)は「No」を出力して終了です。
明日からはD問題に手を出すかC問題をやるかちょっと悩む・・・。
それでは！！
