プログラミングコンテスト「Google Code Jam 2013」に参加しました。
参加したとは言ってもまだ予選が終わったばかりの状態ですが。
コンテストのページはこちら： Google Code Jam
問題文や参加者の回答などは、「Practice」のリンクの「Past Contests」の欄から参照可能です。
Googleがこういうコンテストを開催しているということは耳にしたことはあったのですが、それをいつやっているのかとか、どんな形式でやってるのかという詳しい情報はずっと知らないままでした。
2012年になって、 GeekBear に来られている方々が何人か参加されているという話を耳にして、こういった「競技プログラミング」に興味を持つようになりました。
何を競うのか？
簡単に言うと、アルゴリズムの構築能力を競います。
与えられた問題文（GCJの場合、もちろん英語です）を読み、その問題を解く為のプログラムを作り、問題文に付属しているデータをプログラムに与えて出力を提出する、という形式になります。
このときの
- プログラムの正しさ（＝出力の正しさ）
- 所要時間（プログラムを書く時間＋プログラムの実行時間）の短さ
を競います。
今回の問題
正式なものは冒頭に掲げたリンク先を見て頂きたいのですが、今回の問題は以下のような構成でした。
- A : ○×ゲーム問題（ちょっと変わった○×ゲームの勝敗判定）
- B : 芝刈り機問題（与えられたパターン通りに芝を刈ることができるかどうか）
- C : 回文と平方根（与えられた条件を満たす整数の数を数える）
- D : 宝箱問題（宝箱を開ける順序を決定させる）
AからCは正答率90%程度だったようですが、最後のDの宝箱問題は難しく、正答率は30%程度に留まりました。（いずれもSmall Data Setでの話）
僕の結果
- A : Smallで1回incorrectになってしまいましたが、修正して2回目で無事クリア。Largeはincorrectになってしまいました。後で調べたところ、勝負が継続中である盤面を見たときに誤って引き分け判定を下していました。Smallで通ったのは、たまたまそのパターンのものがデータに含まれていなかったということだったようです。
- B : 芝刈り機の挙動についての英文が１回読んだだけでは理解できず、一旦パスしてしまいました（泣）。後で問題文を読み返したときには理解でき、プログラム自体は比較的楽に書くことができました。SmallもLargeもクリア。
- C : 与えられた閉区間に含まれる整数のうち、回文になっていて、かつ、その平方根の整数も回文になる整数の数を求めよ、という問題。アルゴリズムもなんも考えずに文字通り実装してSmallはクリア。Large1の実行時には処理速度が追いつかずに時間切れで敗北しました。無念。Large2ってどうやって解くんやろ…？
- D : Smallなら全順序をテストして実際に開けることができるものを見つければ良いと思って安直な実装をしましたが、こちらも処理が追いつかず、時間切れで敗北。Small Data Setのものは全数検査のような稚拙な手段であっても解けるものだと思い込んでいましたが、この問題ではそれはありませんでした。正答率30%というのも納得です。
こうして文章に書くと惨憺たる結果なのですが、なんとか予選を通過することができました。順位は全参加者2万1278人のうち、1万800位くらいです。これで「平均的なプログラマ」を名乗っても良いでしょうか（笑）
次はRound1-Aが4月27日に開催されますので、しっかりと予習をしておきたいと思います。
