Google Code Jam 2014 予選

昨年 に引き続き、今年も家族の協力を得て Google Code Jam に参加しています。 27 時間の 予選ラウンド がさきほど終わりました。

成績と提出コードは Scoreboard および Stats で見ることができます。自分 (yaegashi) は 1416 位 (予選開始後 23:23:55 で完答) でした。また自分の作業リポジトリは GitHub にて公開しています。

今年はすべての問題で Ruby を使って回答し、めでたく満点で予選通過できました。高速化のために C++ を持ち出す必要もなく、 昨年 に比べて問題がだいぶ簡単だった気がします。実際今年の満点は 1737 人と 昨年の 63 人 よりも大幅に増えています。

午前中

予選開始は日本時間で 4/12(土) 08:00 でしたが、ちょうどこの日は午前中に息子の幼稚園入園式があり、そっちに出席してました。スタートしたのは昼下がりになってからです。

Problem A

特にトラブルなく回答。 積集合を求めるのに Array の & を使っただけのお気楽プログラムです。こういう問題はやはり Ruby みたいな高級言語が楽ですね。

Small 問題だけだし、何回間違っても別にいいや的な態度で臨みました。午前中の疲労からぐだぐだと取り組んだので 30 分かかりました。

Problem B

Cookie Clicker 問題。このゲームは去年流行したときに自分もプレイしており、ちょうどこの問題と同じような設備投資の最適化について考えていたので、問題の理解は早かったです。

しかしながらやはりぐだぐだしていたので 30 分かかりました。

Problem C

Minesweeper 問題。まず解法を考えるのに時間をとられました。結局クリックするセル座標を (0,0) に固定し、そこから “0” のセルを必要な数に達するまで拡大していく作戦にしたのですが、やはりコーナーケースの見落としがいくつかあって Small で 2 回間違い、正解するまでに休憩や夕食も入れて 6 時間くらいかけてしまいました。

Large は 50×50 のテスト問題を作って試したところ、特に工夫しなくてもいけそうだったのでそのまま実行して提出しました。

Problem D

このあたりになるともうだいぶ眠くて頭の回転が鈍くなっています。

サンプルの入出力結果がなぜそうなるのか最初理解できず、風呂に入り 1 時間くらいそれについて考え、やっぱりまじめに探索やんないとだめそうだなあということで適当に配列 dup しまくりの遅い再帰探索プログラム d.rb を書いて Small を正解。

Large に向けたパフォーマンス向上については 2 時間ほど床で気絶した後にメモ化を使えばいいことをようやく思い出し、配列 dup も避ける実装 d2.rb にしたところいけそうな速度になったのでそのまま Large 提出しました。

16:30 追記: また 2 時間ほど気絶してよく考えたら、 再帰探索なんかしなくてもただの二重ループでいいことに気づきました。眠すぎてほとんど脳が動いてなかったみたいですね。まあ速度を求めて C++ で再実装とか始めなかっただけよかったとしよう…。

まとめ

というわけで今年の Google Code Jam 予選は満点がとれたのはよかったですが、自分の課題であるスピード向上については、まったく取り組むことなく終わってしまいました。

今年はどうにか Round 1 を突破していきたいものですが、この調子ではやっぱり難しそうです。

2014/04/13 22:54:00 JST