PKUで解いたやつの解法とかをメモしようと思うんです

解いた報告ばっかりだとつまらないし、自分が忘れないためにも解法をメモしておこうと思う。

実装ゲーについては解法も何もあったもんじゃないので書かない。

とりあえず普通に解いたらTLEしたりするような、頭を使って解く問題に関してはメモする。そしてこれが第一弾。

PKU 1556 The Doors

これは始点終点と壁の端点をグラフの頂点として、ある点からある点までを直線で結ぶことができるかどうかを線分交差の有無で判定し、ある点からある点まで直線で結べる場合はそのふたつの点に対応する頂点の間に辺をひく。このときの辺の長さには二点間の距離を用いる。

後は最短経路を求めればよい。単一始点なのでダイクストラが使えるが、点と辺の数は多くないのでFloydで十分。実装も楽。

PKU 2002 Squares

全部の点に対して正方形になるかを試すとO(N⁴)でTLEする。

そこで、ある二つの点について、その二つを結ぶ線分を一辺とするような正方形が存在するかを調べる。そうすると二つの点の組み合わせがN(N-1)であり、ひとつの線分について、その線分を一辺とするような正方形があるかどうか調べるのには全点を見る必要があるのでそうすると全部でO(N³)になるが、これもTLE。

ここで全点をソートしておくと、目的の座標の探索がO(logN)で可能なので全部でO(N²logN)になる。これで間に合うはずだが実装が馬鹿だとこれでもTLEする。

O(N²logN)で通すためには、二点i, jを調べるときに i < j の場合のみを調べればよいことと、i < jに限定した場合は同じ正方形が必ず2回カウントされることに気付く必要がある。二点をi < jの場合のみに限定すれば組み合わせはN(N-1)からN(N-1)/2になる。また、正方形の重複判定にsetを使ってると数えるのにlogNの時間が必要だが、全部数えてから2で割ってやれば定数時間で数えることができる。

試してないけど座標をハッシュで持っておけばO(N²)でいけると思う。