■ [GCJ]Google Code Jam 2009 Round1A 
2009-09-12 10:00 - 12:30（JST）
朝はつらい。
問題の難易度的には、去年とそう違いはない印象でした。
| ID | タイトル | small | large | 感想 |
|---|---|---|---|---|
| A | Multi-base happiness | AC | Compiled | 整数。最初に全部計算しといて、各テストケースではテーブルルックアップだけする方針で。 smallでは答がそんなに大きくならないと仮定して100万まで探索して通した。 largeでは、最悪ケースの答が1000万まで試しても出てこないから、アルゴリズムが根本的に違うのだろうと放置。 終了後に、最悪ケースでも1100万くらいで収まると聞いてショックを受ける。 1000万までの計算は1分くらいで済んでるんだからもっと粘るべきだった |
| B | Crossing the Road | WA*1 | - | はいはいダイクストラね。問題文がちょっとわかりづらかった。 つつがなく組んでサンプルも通ったがincorrect。見直す時間もあまりなく終了。 通らなかった原因は、右と上にしか移動していないことでした。思いこみって怖いですね |
| C | Collecting Cards | AC | AC | 確率。Bよりも解いてる人が多かったのでBより先にこっちをやった。 まだ獲得していない枚数をキーにしてメモ化再帰で。 一枚も新しいカードを取れなかった場合の再帰的処理でやたらミスって時間がかかってしまった。 【追記】再帰しなくても綺麗に式を整理できたのか。うまくいかない気がして、収束するまで足し込んでいく複雑なコードを書いてた。そりゃバグ埋め込むわ |
49pt/100pt
270位/2300人くらい→Round1通過のはず
もしA-largeが解けていれば150位あたりでRound2通過圏内。Top500もそこまで無理な話ではない予感です。
全問正解者が65人と意外と少なかった。
