【Python】JOI 2007 本選 3 - 最古の遺跡(①高校数学ベクトル、②「in リスト」は激遅)【AtCoder】

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】(@e869120さん)

こちらの7問目！
難しい！！！
頑張って理解できたので解説〜

JOI 2007 本選 3 - 最古の遺跡

先にACコードから↓

test.py

def I(): return int(input())
def TI(): return tuple(map(int,input().split()))
n = I()
xy = [TI() for _ in range(n)]
set_xy = set(xy)
ans = 0
for i in range(n):
    x1,y1 = xy[i]
    for j in range(i+1,n):
        x2,y2 = xy[j]
        vectorx,vectory = x2-x1,y2-y1
        if (x1-vectory,y1+vectorx) in set_xy and (x2-vectory,y2+vectorx) in set_xy:
            ans = max(ans,vectorx**2+vectory**2)
print(ans)

はまリポイント

大きく2つあると思います。
①前提知識 高校数学ベクトル
②TLEにならないための知識 「in リスト」は激遅！！！

①前提知識 高校数学ベクトル

まず基本から!

ABC108B - Ruined Square

difficulty:140
正方形の頂点4つある。
そのうち2点だけわかっている時の残りの2点を求める問題。

入出力例2の場合

要は、正方形を作りたければ、
1つのベクトルに対して、
xとyを入れ替えてどっちかにマイナスつければいい！！！

今回の問題では、反時計回りと書いているので、
上の図でいくと、
頂点C,Dのそれぞれx座標、y座標を求めれば良さそう！
(頂点E,F側の正方形は考えなくていい。)
ABベクトルに同じ長さで垂直なベクトルは、
(-3,4)
となったので、
Cの頂点は、Bの位置(6,6)+(-3,4)→(3,10)
Dの頂点は、Aの位置(2,3)+(-3,4)→(-1,7)
でいけそう！
コードにおこすとこんな感じ！

test.py

def LI(): return list(map(int,input().split()))
x1,y1,x2,y2 = LI()
vector = (x2-x1,y2-y1)
x3,y3 = x2-vector[1],y2+vector[0]
x4,y4 = x1-vector[1],y1+vector[0]
print(x3,y3,x4,y4)

本題

先ほどの問題(ABC108B)の応用！
1.すべての組み合わせのベクトルを出し、
2.そのぞれぞれのベクトルに対して、垂直ベクトルを出す！
→そのとき、垂直ベクトルの先に下図で言うXとYが2つとも重なれば、正方形となる！！！

後は気合！
そこまでベクトルを恐ることはない！
ベクトルはただの矢印だ！

②TLEにならないための知識 「in リスト」は激遅！！！

以下のコードだと、TLEになる。(PyPyでも同じくTLEになる。)

TLE.py

def I(): return int(input())
def LI(): return list(map(int,input().split()))
n = int(input())
xy = [LI() for _ in range(n)]
ans = 0
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]
        vectorx,vectory = x2-x1,y2-y1
        if (x1-vectory,y1+vectorx) in xy and (x2-vectory,y2+vectorx) in xy:
            ans = max(ans,vectorx**2+vectory**2)
print(ans)

↓この部分が重たすぎるのだ・・・！

if (x1-vectory,y1+vectorx) in xy and (x2-vectory,y2+vectorx) in xy:

参考の記事
・Pythonistaなら知らないと恥ずかしい計算量のはなし
・【python】in演算子は遅いのか？

計算量を気にするときは、inの後ろは、ハッシュテーブルを使ってるsetやdictにしよう！
じゃあ、xyをsetにしてあげようね〜

実行時エラー・・・
5行目で、listはハッシュ化できませんだと・・・

参考の記事
Python における hashable

要は、
・immutable(変えられない！)であるint, str, tuple, frozenset は hashable
・listは、hashableではない
ということ！

str = 'abc'
# strは、immutableなので、こんなことできない！！！
str[0] = 'x' 
#TypeError: 'str' object does not support item assignment

list = ['a','b','c']
list[0] = 'x' #エラーは起きない！

よって、
入力のところをlistではなく、immutableでhashableな
tuple
にしてあげた！

def I(): return int(input())
def TI(): return tuple(map(int,input().split()))
n = I()
xy = [TI() for _ in range(n)]
set_xy = set(xy)

やっとのことで、AC！！！
お疲れ様でした〜

おわり！