【競プロ典型 90 問】009 - Three Point Angle

Arakaki Tokyo -

米田氏が企画した「競プロ典型90問」を解いていきます。

ここでは私の試行錯誤やら解説の理解やら気づきやらをメモしていこうと思います。 競プロ初心者なのでどうか温かい目で見守ってください。

なお、本記事中のPythonコードはブラウザ上で実行可能です。 よろしければ遊んでいってください。

問題

kyopro_educational_90/009.jpg at main · E869120/kyopro_educational_90

try

考え方

  • $N$個から3つの組合せ全て検討してたらTLEだろうなぁ
  • 統計分析っぽく、単回帰から誤差の小さい順に3点を結べばよいのでは！？
  • いやいや、別に全体のデータの傾向なんて関係なくて、離れた3点が直線に近かったらそれが正答だもんな…
  • とりあえず各点の傾き出して、近い3点を選んでみるか？
  • いやいや、原点を通る直線に近似する訳じゃないし…

分からん！

という訳で早速解説を見ます。

テストデータ・テスト関数だけ定義しとく　↓

# 縮小表示 test_data = [ { "in":[3, [[0, 0], [0, 10], [10, 10]]], "out": 90 },{ "in":[5, [[8, 6], [9, 1], [2, 0], [1, 0], [0, 1]]], "out": 171.869897645844 },{ "in":[10, [[0, 0], [1, 7], [2, 6], [2, 8], [3, 5], [5, 5], [6, 7], [7, 1], [7, 9], [8, 8]]], "out": 180 },{ "in":[40, [[298750376, 229032640], [602876667, 944779015], [909539868, 533609371], [231368330, 445484152], [408704870, 850216874], [349286798, 30417810], [807260002, 554049450], [40706045, 380488344], [749325840, 801881841], [459457853, 66691229], [5235900, 8100458], [46697277, 997429858], [827651689, 790051948], [981897272, 271364774], [536232393, 997361572], [449659237, 602191750], [294800444, 346669663], [792837293, 277667068], [997282249, 468293808], [444906878, 702693341], [894286137, 845317003], [27053625, 926547765], [739689211, 447395911], [902031510, 326127348], [582956343, 842918193], [235655766, 844300842], [438389323, 406413067], [862896425, 464876303], [68833418, 76340212], [911399808, 745744264], [551223563, 854507876], [196296968, 52144186], [431165823, 275217640], [424495332, 847375861], [337078801, 83054466], [648322745, 694789156], [301518763, 319851750], [432518459, 772897937], [630628124, 581390864], [313132255, 350770227]]], "out": 179.9834340684232 } ] def test_all(f): for i, data in enumerate(test_data): exp = data["out"] ans = f(*data["in"]) result = "AC" if exp == ans else "WA" print(f"{i+1} {result}: expected: {exp}, output: {ans}")

解説・想定コード

kyopro_educational_90/009.jpg at main · E869120/kyopro_educational_90

想定コード： kyopro_educational_90/009.cpp at main · E869120/kyopro_educational_90

理解する

ふむふむふむふむ…
天才か！！

私のような凡人だと『3点　角度』とかでググって、どうやらベクトルの内積の公式から$\cos\theta$を求めて角度が分かりそう、ぐらいまでのことしか思いつきません。曰く、以下。

$$ \vec{ a } = (a_1, \ a_2),\:\: \vec{ b } = (b_1, \ b_2) とおく。 \\ \begin{matrix}\\ \vec{ a } \cdot \vec{ b } & = |\vec{ a }| |\vec{ b }| \cos\theta \\ & = a_1 b_1 + a_2 b_2 \\ \end{matrix}\\ 内積(\vec{ a } \cdot \vec{ b })の公式より、\\ \cos\theta = \frac{a_1 b_1 + a_2 b_2}{|\vec{ a }| |\vec{ b }|} $$

しかし、このような計算を行うためには3点を確定させる必要があり、どうしたって$O(N^3)$の呪縛から逃れられません。

そこで偏角ソートという考え方が必要になるのです！

まず真ん中の点(B)を決めて(N通り)、その点を原点としたときの他の点の偏角を求める。
これなら2点を確定させるだけで算出できます。
そして算出した各点の偏角をソートすることで、$O(N \log N)$でもっとも点対称に近い2点を探せるという訳です。

上の解説の内容を繰り返しただけになりましたが、心底感心したので自分の言葉で言い直しました😇

実装する

想定コードをPythonで書き換えたのが以下です。
今回はクラスや演算子オーバーロードなどがあって、なかなか凝った作りですね。

コードの見通しが良くなる、デバッグしやすくなる、などメリットは多いものの、やはり競プロ的には実行時間の圧迫が懸念されるところですが…。
インスタンス化にあたってあまりにも重い処理をしない限り、そんなに心配しなくていいかもしれませんね。

import math from bisect import bisect EN = 2*math.pi class Point(): def __init__(self, x=None, y=None): self.x = x self.y = y self.norm = (x**2 + y**2)**(1/2) if self.norm: angle = math.acos(x/self.norm) if y < 0: angle = EN - angle self.angle = angle else: self.angle = 0 def __sub__(self, a): return self.__class__(self.x - a.x, self.y - a.y) def __repr__(self): return str((self.x, self.y)) def main(N, A): A = [Point(*a) for a in A] ans = math.pi for mid in A: ends = [(a-mid).angle for a in A if not a is mid] ends.sort() for end1 in ends: i = bisect(ends, (end1 + math.pi)%EN) if i == len(ends): i = 0 ans = min(ans, min(*map(lambda x: abs(end1+math.pi-x), [ends[i], ends[i-1]]))) return math.degrees(math.pi - ans) test_all(main)

設問では『相対誤差または絶対誤差が$10^{−7}$以下』とのことなので、4つ目のケースも大丈夫そうです。

結果：無事AC

提出 #32684644 - 競プロ典型 90 問

まとめ

現状、★6以上は手も足も出ないな…

自由欄