先週の土曜日にGoogleCodeJamJapan2011がありました。GoogleCodeJamの過去問は今まで見たことあったけど、英語で問題書かれてて、見るのも疲れてやる気は出なかった。今回はGoogleCodeJamJapanと銘打って、問題も全て日本語で書かれているということで、初めて参加してみた。
遅くなってしまったけど、自分の記録の為にも残しておこうと思う。
予選
参加自体始めてで、正直問題が発表されたときはドキドキだった。でも6時間ぐらい猶予あったから、のんびり考えることに。左に早く解答した人がどんどんスコア伸ばしてるのを見て、正直あせりしかなかった。
問題A. カードシャッフル
Pythonでコーディングすることは決まってたので、シャッフル自体は配列でスライシングをすれば簡単にできそうだったので実装。doctestも書きながら、慎重にこなす。smallはクリア。ただ、計算量のオーダとか全く考えてなかったので、
large問題にもそのまま使おうとすると、メモリ不足でハングアップ。large問題は1回しか解答できないので、問題Aはここであえなく終了。
問題B. 最高のコーヒー
至極わからん。飛ばす。
単純に満足度の一番高いやつを選んでいくアルゴリズムにしたけど、テストケースすらクリアできない。あとで他の人の解答見たら、最終日から順に前に戻って考えていくらしい。
問題C. ビット数
決勝に進む条件は一つ以上のsmallとlargeのセットを解くということだったので、これが解けないと予選敗退。決勝進出の条件自体は予選終わってから聞いたのだけれど。
いろんな数で、総当りで検索すると、規則性に気づく。その規則性を実現するようにアルゴリズム実装すると、largeも解けそうなことに気づく。問題A落としてるだけあって、今回はlargeも慎重に解いた。
small問題(総当り)
large問題(むりくりあみだした)
ぐだぐだやって4時間ぐらい。問題Bも考えてみたけど、わかりそうになかったから諦めてしまった。
ここまでで、スコア23の順位450位。まあ楽しかったなーと思いつつ、すごいやつらがごろごろしててちょっとショックだった。いい経験だったとまとめようと思ったら、ここにきて決勝進出の条件を知りテンションが上がったことを覚えている。
久しぶりのブログ。また決勝は別の記事でかこ(´・ω・`)