JOI2010本戦 結果やら感想など

東京に遠征してまいりました。

結果：オタワ＼(＾o＾)／

正解ソースコードとかはid:qnighyさんがやってくれてるので自分は省略。
http://d.hatena.ne.jp/qnighy/20100215/1266241180

１（旅人）：模範解答とはちがったけれどO(m+n)なので普通に通った
２（おかし）：ＤＰ厨の本領を発揮したので解けた
３（つらら）：priority_queueをつかってO(nlogn)で解けたとおもったら自作のn>10000のデータでSEGVった。結局原因が分からないので放置。データセットによるけど５０％は取ったはず
４（博覧会）：n<=100000なのでO(n^2)は通らなさそう。→じゃあ各点間の距離計算出来ないじゃん→ｳﾎﾞｧ→仕方ないからO(n^2)で４０％を狙うか→・・・アレ？
解説を聞くに、座標を４５度回転したら簡単な問題に帰着するっていう閃き一発の問題だったらしい。
二部グラフ判定と距離での二分探索をつかったO(n^2log距離)の部分点ぐらいは取れても良かったかなぁと後悔。
５（ダンジョン）：「もしかして：ＤＰ」→n<=100000→ｳﾎﾞｧ→とりあえず回復量の多い泉から使えばO(使用回数logn)なんじゃね→回復量が同じだったらどっちから使えば良いんだorz→じゃあ上から順番に潜っていったらO(n×なんとか)でうまいこと行けばO(nlogn)になるかも→どうやったら最適になるんだｗｗｗ
解説によると上から順番に潜っていくという発想自体は当たっていたらしい。解説の時はよくわからなかったけれどとにかくdequeを使うようだ。そのうち理解する予定。

こんな感じで、予想点数は20,20,10,0,0の50/100。
合宿行けるかどうかヒヤヒヤだ〜
発表が見たくない！

その他：
去年合宿で一緒だった人たちとか、twitterの人たちとかいろんな人に出会った。JOIはオフ会みたいなもんだ。
懇親会でtwitterer挙手の流れになったときに、半数弱ぐらいの手が上がっていてビビるなど。twitter恐ろしい。
Aizu Online Judgeがオススメされていた。日本語問題は嬉しい。ぼちぼちやっていこう。

とりあえずPKUやらAOJなんかは実装ゲーじゃなくて解き方を考えつくまでが勝負な問題を優先してやって行く予定。合宿通ってないと意味ないけど。

しょうもないこと：
談話室にいる間、iPhoneでPKUのクソ問を解いていた。JOIには全く役に立たないが暇つぶしにはよさげ。目でコンパイル（笑）