JAG summer camp 2010 - komiyamの日記

うろ覚えだけど覚えている分について書いてみる。

day1

某所でおいしい昼食をとった後、オリンピックセンターへ。競技プログラミングの世界での有名人が集まっているのを見て少し気後れする。
Practice Sessionが始まる。冗談でBからやろうぜ、とか話していたらhasiが本気で取り組む。
周りは和やかなのんびりとした雰囲気。なんか楽しそうなことやっているなあ、と眺める。
hasiがBを嘘解法で通した。しかもfirst accept。残っているAをさくっと通して1位をとる。もうこれがアジア予選でいいんじゃないかな。
部屋割りはhasiと同室だった。部屋割りは合宿常連組みいわく、かなり作為的なものらしい。

day2

問題は日本語らしいので気分的には楽な状態で開始を迎える。
開始しても相変わらず雰囲気は和やか。さすがに他のチームと会話しているのはなかったけれど。
Aをhasiが読む。Bをimosが読む。自分は幾何がなかったのでDPっぽいDを読む。
hasiいわくAはすごく簡単らしい。hasiのコーディング中にimosがBを解けたらしい。
imosにCが簡単っぽいと言ってCを投げる。Cも幅優先するだけだと言っていたのでグラフっぽいEを投げた。
Aが無事通った。imosがBに取りかかる。hasiはFに取りかかる。
imosはBにちょっと苦戦している。自分もDがまったく解けない。
このあたりはhasiも自分も苦戦していた。hasiは小さいケースを手で解いて法則を見つけようとしていた。自分はというと、あまりの進まなさに少し集中力が切れかけていた。
その間にimosがB,Cを通す。
imosにEは幾何と言われて返される。そしてimosにDを投げた。
Eにとりかかる。問題文を、交わらない全域木をさがす問題だと勘違いする。当然そんなものが通る筈もなく、WAを貰う。
他のチームがEをたくさん解いているので、気づけばすぐに解ける筈だと思って考慮を続ける。
imosがDを通す。imosにEを相談すると、問題文の解釈が間違っていることと、重要なヒント(経路の片方は必ず直線になる)を教えてくれた。
さすがにそれだけヒントを貰ったら後は実装するだけ。無事Eを通す。
hasiもimosにFを投げる。imosがGは二分探索するだけ、と言ってFに取りかかった。
残り時間が迫り、imosやhasiがG,Fに取り組むが解けずに終了する。Fの問題の制限の一部をimosが勘違いしていたことがコンテスト終了後に判明。
結果は5ACで4位/8。
チームの足を引っ張りまくって、実質1問も解けなかったことにかなり凹んだ。
こうして箇条書きにするとimosの貢献度が大変なことに気づく。

day3

day2がアレ過ぎたので今日こそはという覚悟で望む。
Aをfirst accept狙いでimosがとき，hasiとkomiyaで解けそうな問題を探す。
komiyaはBにとりかかり、hasiはEに取りかかる。hasiのEはGreedyだと当たりをつけていた。
imosがAに苦戦している中、Bがグラフっぽいのでimosに回して解けそうなFに取りかかる。
どう見てもビットDPなのでそれらしいDPのアルゴリズムを紙コーディングする。
Aが通ったのでimosにBを投げる。
hasiがコーディングを開始する。komiyaはもうFを解き終わった気になっているのでhasiのデバッグを手伝う。
Eは実はそれほど簡単なgreedyでは駄目らしくて、hasiが再考している間にkomiyaがFを打ち込む。
Fがsample通ったのでsubmitするもWAを連発。問題文を読み直すとクリティカルな読み間違いを犯していることに気づく。さすがに2日連続だったので少し心が折れた。
Eをhasiが通した。しかもfirst accept。komiyaはhasiにFの援助を要求した。
当時は情けないという思いでいっぱいだったけど、チームに迷惑をかけないためにも当然そうするべき処置だった。
直後にimosがBを通した。standingを見て、imosがJに取りかかった。
hasiはFを再帰で書くことを提案した。hasiに投げると、確かにsampleを通すコードはすぐにかけた。
submitしたらTLEを喰らった。計算量が2^28とはいえ、ローカルでは最悪ケースで1秒をちょっと越えるくらいだったので定数倍最適化を目指す。
komiyaやhasiがビット演算への変換や再帰関数の呼び出し回数を減らすのに苦慮している間、imosはJにハマっていた。
この辺でやっていた定数最適化はかなり楽しかった。
制限時間ギリギリでFが通った。その後hasiはimosのデバッグを手伝い、komiyaはAC数の多いHに取りかかった。
hasiの指摘によりコーナーケースを回避してJが通った。imos、hasiもHに取りかかる。
全員で考えるが時間が切れてコンテストは終了。5ACで4位/8。
反省すべき点は多すぎるけど、努めて自虐的にならないようにした。

day4

ここまでチーム10ACの内6(実質7)ACを叩き出したimosが抜けて不安に駆られる。
day4は問題文が英語なので、3日連続でやらかすんじゃないかとさらに不安が募る。
事前に決めていた通り、Aをkomiyaが取り掛かりhasiはC以降を読む。
hasiはDがやるだけだと言っていたのでhasiにDを任せる。
Aに対してまともにアプローチしていたり、Bに軽く目を通しているうちにhasiがDを通す。
皆が解いているB問題についてhasiに説明する。計算量の解析は難しいけれど、皆通しているから愚直にやっていいだろうと見切りをつけてhasiがBをコーディングし始める。
Aが閉路圧縮(縮約)の部分問題を除いて解けた。閉路圧縮ぐらい手抜きな方法でも大丈夫だと踏んでバグを埋め込む。
Bが何事もなく通る。komiyaはhasiに閉路圧縮を投げる。
hasiが丁寧に閉路圧縮を実装してAを通した。
CとHが解かれていたので、解ける希望のあるCをkomiyaとhasiで考える。
hasiが閉路検出の部分問題をkomiyaに投げて来たのでアリ本で調べる。
何となく目に止まったMSTのページを見て、辺を取り除いたら木になるんじゃないかと考える。
証明はしていないけど最大全域木を作ればいいので、それでコーディングを開始する。
hasiはunion-findがかけなかったのでコーディングをkomiyaが担当する。
キーボードの関係云々でタイピングが余りに遅すぎたので、タイピングをhasiに投げる。
コードを喋りながらタイピングをさせる図というのはさぞかし滑稽だったに違いない。
無事Cが通る。ノルマの4問が解けたことに安堵する。
残り時間でHに手をつける。残り時間も少ないのでありえない位都合のいい仮定を置いて嘘解法をでっち上げる。
しかし所詮嘘解法なので当然WAで弾かれる。
そのまま終了。4ACで6位/9。imos抜きの割に頑張ったと思う。imosなら多分Hは解けていたはず。

反省

問題文はちゃんと読め。
チームメイトが優秀なんだから助けを求めることをためらわない。簡単な問題に時間をかける方が他人の時間を奪うよりずっと悪。
タイピングがありえない位遅い。
メンタル面の強化が急がれる。