World Finals

なんとまぐれで３位を取ってしまった！！！

開始

なんか点数の割り振りがすごく偏っているが気にせずとりあえずAから読むことに
読んですぐ方針は立ったので組んでみたがなんかバグってサンプルが通らないorz
最近はICPCの影響でバグ取りがめんどくなってきたので放置して他の問題やることに

Bを読んだらこないだの台湾大会の問題となんか似ている…
とりあえずこないだと同じ嘘解法すればsmallはいけるんじゃね？と思ったがTLEしたorz
まぁちょっと改良すればいけそうなので放置して次へ

Cはsmallはやるだけでlargeはさっぱり分からない…次へ

Dのsmallが全問題中一番点が低かったのでとりあえず通しておくことに
small書いてる途中で、あれこれただのフローじゃんってなったのでlargeもすぐに通った

1時間経過

Eを読んだらlargeはさっぱりだけどsmallはやるだけな感じがしたので組むことに
サンプルは通ったのにsmall通らねーというわけで放置して次へ

やたらと点数の高いFを読んだら幾何ktkrってなって実装開始
なんかバグったので例のごとくVisualizerを作成してデバッグ

途中気分転換にEに戻ったりしてた

2時間経過

ようやくFのsmallが通った
まぁlargeも通るに違いないと信じて時間が余ったら見直してから提出しようと思って放置してBに戻ることに

周囲の長さ最小の三角形ってドロネー三角形のどれかなんじゃね？とか思い始めてそんなの組めねーってなった
とりあえずマンハッタンでのドロネー図っぽいやつは昔実装したのがあったのでそれコピって出してみたらなんか通ったｗ
さすがにlargeは通らなそーだなーと思いつつ放置してAに戻ることに

3時間経過

なぜかどうしてもサンプルが通らず、よーく見たらClarが出てることに気付き、入力の解釈間違えてたorz
そこ直したらようやくサンプルが通りsmallもlargeも通った

残り時間が少なくなってきたのでやるだけなC-smallをてきとーに通し、B-largeをやってみることに
だいたいO(n log n)の嘘解法だけどTLEしたorz
最後にF-largeをやってみることに
large動かしてみたら、なんか解の正しさチェックが落ちている…
なぜだーと思ったらバグ発見！！！
急いで修正したものの直しきれずTLEorz

終了後

Eの問題文勘違いが発覚orz
暫定順位が6位でE-small通してれば3位だったので鬱になってたが、なんか他の人のが結構落ちてまぐれで３位獲得ｗ
しかしACRushにダブルスコアされたのでやっぱり鬱

ホテルに戻ってからFのバグを取ってみたが、今度は円と多角形の共通部分面積あたりで誤差ってるぽくて正しい解が出なかったので、まぁしょうがなかった

Bは最近点対と同じような分割統治をすればよかったぽい
最近点対知ってるのにこれ解けないとか終わってたorz

Eは帰りの機内で考えてたらてきとーにDPすればいけそう
Cは知らない