Saratov school team programming contest 2011
平日昼間の開催だったけれど、ちょうどhasi君が研究室の近くに来ていたのでふたりでチームを組んで参加した。これまではチーム名をICPCの頃の名残りでImoにしていることが多かったけど、imos君がいなくなってしまったので新しくチーム名をPotatoにしてみた。以下コンテストの流れ。
- 開始前にhasi君とチーム名決めなどをする。研究室近くのお茶飲み場で参加することにした。
- 自分はミーティングで参加が20分くらい遅れたけど、その間にhasi君がA,Bを通していた。Cもやるだけらしい。
- ちょっと準備している間にCが通された。その流れでhasi君がDを読み、自分がEを読む。
- hasi君と自分で問題内容を説明しあった。hasi君に「DはどうせDP」とか言ってDPを書いてもらう。
- Eを勘で通した。hasi君はDでちょっとハマっていた。
- もう一度問題を聞いてみたところ全探索が余裕なことに気づいたので全探索で書き直してもらう。DPとか言ってほんとすいませんでした。
- Fを読むけど、読めない。
- Dを通したhasi君にFを読んでもらう。その間に自分はHを読む。
- Fを解読したhasi君に話を聞くと、木の直径らしい。自分が解き方知っていたのでhasi君に説明して、実装を任せる。
- Hは読めたが解法は分からない。Gを読んでみる。読めない。
- Fを通したhasi君にGを読んでもらう。その間にJを読む。
- 最初、最小と最大を読み間違えていた。凸包と凸多角形の直径ライブラリを貼り付けるものの間違っていて動かない。
- hasi君にデバッグ手伝ってもらってたっぷりと時間を消費した後、最小だったことに気付く。
- hasi君がシミュレーションらしいGを書いている間に自分はO(N^2)の最近点対を書く。当然TLEする。
- Gが通されて、Hも多くの人に解かれていたからどうせテストデータ弱くてgreedyで通るとか言ってgreedy解を書いてもらう。
- 分割統治なO(N *log N)の最近点対があるのは知っていたけど、手元には擬似コードしかないのでこの実装はhasi君に任せることにする。
- Hがgreedyで通されて、hasi君に擬似コードでかかれていた最近点対を実装してもらう。
- 自分は最近点対以外の入出力の部分とかデータ変換の部分を書いていた。
- 最初は真面目に4箇所にマップされた点を考えていたけど、全部第一象限に集めてよさげなことに気付いた。
- 修正する。最近点対のデバッグして、無事タイポしてる部分を見つけてJを通した。
- 結局自分はE(実装量ほぼゼロ)しか書いてないけど、世の中には適材適所と言う言葉もあるのでこれでいいことにする。
- でもさすがにFくらいは自分が引き受けてもよかったような。
