Google Code Jam 2011 World Final
トーナメント型のコンテストでは初のオンサイト参加でした．
http://code.google.com/codejam/contest/scoreboard?c=1327485#vf=1
結果は14位でした．
コンテスト中
- 開始して問題文を読む
- Aをちょっとだけ考えるが分からない．しかし頑張れば解けるだろうという気がするのでBを読む．
- Bを読む．読解でちょっとはまって時間をロスする．smallはただのシミュレーションだがlargeは全く分からない．得点が低いのでやることがなくなったらやることにしよう．
- Cを読もうとするがなんとなく嫌な雰囲気を感じて飛ばす．
- Dを読む．問題の意味がよくわからないが，smallは全探索っぽいし読解さえできればできるっぽい．得点も高い．ちょっとだけ考えて放置する．
- Cに戻る．要するにチューリングマシンの問題なのだということに気づく．なんか講義でこういうことやらなかったっけ? いや，全くやっていないと思う．全然見当つかないがちょっと考えればできるのかもしれない．あとで考えることにする．
- Eを読む．読解にやや苦戦する．なんかとりあえずmaxがいっぱいある風の漸化式が立つが，依存関係がひどくて直接計算すらできないように見える．なんじゃこりゃ…
- とりあえずA:small,large B:small C:small D:small? E:small という方針でいこうと考える．ここまで30分くらいだったかなぁ
- Aをしばらく考えるがよくわからない．
- 前から見ていくのは余裕で駄目で，じゃあ最初に"a"を全部置いて，次に"b"を置いて，…とかやるといいんでは? と思うがこれもうまくいかなさそうな気がした．(しかし実はこれでうまくいく)
- 結構考えても分からないので他のに着手することにする
- Cを見る．しかし全然わからない．無理ゲーなんではという気がしてくる．実際ほとんど誰も解いていない．
- E，どうせN<=20だしどんどん解を改善していく方針にすれば収束するんちゃうの??
- 理由全然わからないけどとりあえず書き始める
- 書いた，サンプル合致してくれた．
- 提出，通る (E small +20pts, 1:44:21)
- 次にDを見る．こういうのは日常の言葉にすると平易だが数学的な言葉で書こうとするとなんか難しい気がする…
- よくわからないので丁寧に解析する．頭いい人ならすぐわかるんだろうけどなぁ…
- 色々バグりながらもサンプルを通す．提出する．WA．ええ… いや合ってるだろう(傲慢)．
- そういえば，途中の状態で， 「??3?2?9???」 みたいな風になっているとしても実はinvalidであることってあるな．ざっくりいうと解析がまだ甘い．
- 判明した列について条件を反してないか調べればいい? 直す．WA．
- もっとちゃんと判定するようにする．提出．ようやく通る． (D small +20pts, 3:08:04 + 2 wrong attempts)
- 終了までもう30分しかないので諦めてB smallをかき集めに行く．
- 終了10分前に提出!! しかしWA…
- 理由わからない．終了．
感想など
15位以内を一応目標にしていたような気がするので自分的に満足のいく結果ではありますが，A問題も気づけば解けそうな雰囲気ではあったのでできれば解いておきたかったです．
rng_58さんは優勝おめでとうございます．
コンテスト後はtwitter等で応援を頂いていたのを見ました．ありがとうございました．
