Google Code Jam2010事前準備メモ

(2010/05/10 追記 2010年分を反映)

この記事を読む前に、こちらに目を通しておくこと。去年の内容だが基本的に変わらない。

Google Code Jamって何?

Google が主催してるプログラミングコンテスト
多分採用活動の一環でもある(後述)。
予選、1〜3回戦、決勝まである。
決勝以外はオンラインで実施。決勝は年によって場所が異なる(今年はダブリン)
今年は5/7から予選開始。

公式

特徴

全言語使用可能

多分この手のプログラミングコンテストでは珍しい。(あまり詳しくないから知らないけど)
そもそも自動判定に使うデータは出力ファイルのみなので、標準入出力と文字列処理程度できれば多分自作言語とかでもいけるんじゃなかろうか。
ソースコードの提出は必要。場合によっては後で文句つけられることもある。ていうか実際去年日本人で誰かそんな人いたような(問題なかったみたいだったけど)
予選じゃPythonRubyといった著名なものからLisp,Haskellなんて関数型言語、果てはシェルスクリプトBrainfuckで提出などという猛者もいる。
しかし決勝になるとほとんどC++Java

入力ファイルを元に出力ファイルを作成して提出するだけ

ほんとこれだけ。入門書を一通り勉強してさえいれば参加できる。
新言語の習得の補助とすることもできる、というか私がそういう目的も兼ねて参加している。今年Pythonを使うつもりだが、まだPython歴1ヶ月ほど。

もう少し具体的に書くと、最低限以下の知識はあった方がいい、というかほぼ必須。

  • 標準入力から文字列を読める
  • 文字列を配列に変換できる(いわゆる split)
  • 配列処理ができる
  • 文字列を数値に変換できる
  • 数学関数、数学ライブラリが使える
  • フォーマット出力ができる(いわゆる printf)
  • 制御構文(for とか if とかのお決まりのやつ)


「それすらできません。Hello World!」とかいう人も心配無用、後述の過去問を解いて過去の参加者のソースコードを写経していれば自然に覚える。

全部英語

当たり前。英語が苦手な人は頑張れ。
ちなみに私は去年英語を誤訳して問題文読み違え→終了というベタな失敗をしてしまった。

参加方法

先述の公式サイトで「Participate」というボタンを押すと登録フォームが出るので入力する。
注意事項をいくつか挙げる。

ニックネームは変更不可

一度決めたら二度と変えられない。メーリングリスト上でも何度もそういう質問が出て、何人もGoogleに問い合わせているがこの件についてはなぜか一切返答がない。あきらめてそのニックネームを使うこと。
さらに、翌年になって別のメールアドレス+去年のニックネームで登録しようと思っても登録できない。去年のデータが記録上残っているようだ。というか私のことなのだが、この件について問い合わせしたのだが半月経っても一向に返信がないのであきらめた。

好きな言語について

別にそこで決めた言語しか使っちゃいけないというわけじゃない。気楽に登録しよう。

実名・実住所?

万一決勝に残った場合は航空チケットが送られてくる。残る気があるのなら正確に登録すること

採用活動

「ねえねえ、もしぼくらからオファーとかきちゃったらさ、どこで働きたいと思う?」

とか聞かれる。

自分の行きたいと思うところを適当に選んでおけばいい。

もちろん、自分の会社ラブ! Google 興味なしという人は「いかねーよ」とかの選択肢があったと思うのでそれ選べばいいと思う。

その他登録まわりで気づいたこと

Google関係者は参加不可。既にGoogleのサマーインターンに行くことが決まってるんだけど、参加していいの? という質問がMLに流れていたが、去年そういう人がいたけど大丈夫だよという人と、いややめた方がいいんじゃね、という人がいた。気になる人は問い合わせた方がいい。

コンテストの形式

スケジュールは公式を見ること。大体3ヶ月かかる。長い。UTCなのでJSTに変更して時刻を見る必要がある。明け方とか夜中とか普通にある。

(2010/05/05追記)自分用にスケジュールを記載。正式な時間は必ず公式を見ること。何か問題が発生しても一切責任は負いません。

QR 2010/05/08 Sat 08:00 - 2010/05/09 Sun 08:00
1A 2010/05/22 Sat 10:00 - 12:30
1B 2010/05/23 Sun 01:00 - 03:30
1C 2010/05/23 Sun 18:00 - 20:30
2 2010/06/05 Sat 23:00 - 2010/06/06 Sun 01:30
3 2010/06/12 Sat 23:00 - 2010/06/13 Sun 01:30


一応賞金が出る。が、気にしなくていい。どうせとれないぶどうなので酸っぱい味しかしない。

以下は2009年までの形式。今年はどうなるか知らない。


共通

問題には必ずSmallとLargeがある。Largeの方がデータとして大きい(値そのものもデータセットの数も)。それぞれに点数があり、Largeの方が点数が高い。
同一点数の場合は早く解いた方が上位にランクされる。
問題のサイトから入力ファイルをDLし、データ処理後出力ファイルをアップロードする。
Small と Large で形式が若干異なる。
Small を答えないと Large を回答することができない。(2010年)


注意しなければならないのは、入力ファイルダウンロード後に制限時間があるということ。練習モード(後述)だとこれがないので知らないと本番でいきなりびびることになる(私のこと)。
Small の場合は制限時間をオーバーして提出できないと-4分だかのスコア上のペナルティ。別に試合時間そのものが減らされるわけじゃない。
逆に言えば、1ペナルティ覚悟で入力ファイルを落としてきて、じっくりコーディングしてエラーが出ないことを確認してから提出するということもできる。上記の通り、早く解くことよりもより高い点数を出すことの方が重要なので、このやり方は非常に有効と思われる。
ただしこれは Small の話。 Large は制限時間 8分、1発勝負である。
これは非常に注意しなければならない。なぜなら Large は文字通り、中のデータセットが巨大だから。
Small を余裕で通ったコードでも、Largeだと制限時間オーバーなんてことはざら。
おまけに Large は、正解・不正解はそのラウンド終了までわからない。これがかなり怖い。
Small は、解けないと Large のデータをダウンロードできないということもあり、提出してもすぐに正解不正解がわかる。


試合中に他人との相談がばれたら即失格。ネットでうかつなこと喋らないように。
といっても所詮オンラインなので、オフラインで相談してばれることはほぼ100%ないだろう。
何が言いたいかというと、自分の技術者としてのプライドと相談してからそういうことをやれということだ。

予選

制限時間24時間。問題3問。
こういうコンテスト初経験の私でさえ通るぐらいなので、それなりに簡単(1問のLargeだけ間違えたけど)
確か足切りがあったと思う。1問解けば通ったはず。
2010年では Small、Large それぞれ1問解けば通った。

1回戦


3試合あり、どれか一つで上位1000位ぐらいに入ればよかったはず。さらに1回戦突破していない人は3試合全てに挑戦できる。(2010年も同じ)
去年私はここで沈んだ。

2回戦以降


日本で有数のプログラミングコンテストの実力者でさえ2回戦でぽんぽん落ちる程度の難易度だと理解していればいいんじゃなかろうか(他人事)。

練習方法

過去問を解く

TopCoderもやらないような人は、これぐらい解かないと話にならない。未登録の人は公式サイトの「Participate」ボタンの右下に入り口がある。登録済みの人はボタンに「Practice」と書かれてるはず。
開くと、左に過去問一覧がずらりと出る。
以下、2009予選を例にとる。ちなみに予選予選と言っているが、これは私が勝手にそういってるだけのことで、正確には「Qualification」である。

http://code.google.com/codejam/contest/dashboard?c=90101#

開くといきなりA問題が出る。
small.inとかlarge.inというのが入力ファイル。DL可能。
Submitを押せば出力ファイルをアップロード可能。正解・不正解も判定できる。

右側にメニューがあり、A,B,Cと問題のタブがある。選択すれば該当する問題を表示できる。
「Contest Analysis」は問題の解説と、場合によっては解答例が書いてある。知らないとまず気づかない。
「Question asked」は本番中に出た問題に関する質問。本番中も随時アップロードされるので注意は払っておくこと。
Submissionsは得点配分と、その時点でのファイル提出ユーザと正解ユーザを表示してくれる。気にする必要はない。
Top Scoresはそのままなので省略。
Full scoreboardを見ると、全ユーザの得点一覧と提出したソースコードのDLリンクが見れる。が、ここでコード探すのは時間の無駄なのでやめること。代わりに別サイトのStatを使った方がいい。

Code Jam Language Stats

2008年: http://www.go-hero.net/jam/08/
2009年: http://www.go-hero.net/jam/09/
2010年: http://www.go-hero.net/jam/10/

言語別、国別にユーザ表示できる。公式のFull scoreboardだと、どのユーザがどの言語を使っているのかわからないが、ここだと一発で発見できる。

まずLanguageをクリック。Select a roundと出るので自分の見たい問題のラウンドを選択。
言語一覧が出るがまだ言語をクリックしない。問題名をクリック。
それから言語をクリックすると、その問題をその言語で解いた人のランキングが表示される。後は見たいユーザをクリックすれば、その人のコードをDLできる。
上位ユーザのコードは特に参考になると思うので見た方がいい。Pythonだとzibadaさんという方のコードはとてもきれい。この人はPython1本で2008年は決勝、2009年は3回戦まで進んでいるすごい人。
ただしこの人でさえ、2008年の予選のコードはあまりきれいじゃない。多分初めてのGCJで勝手が分からなかったのだと思う。おそらく他のユーザにも言えることだと思うので、ソースコードを見るときは2009年の方から見た方がいい。

日本人ランキング

http://www.halwhite.org/ranking.txt

TopCoderとTopCoder部

年がら年中こんなコンテストを開催しているTopCoderというサイトと、参加者のはてなグループ
詳しくはグループの方を見ること。

http://topcoder.g.hatena.ne.jp/

ちなみに私はTopCoderはユーザ登録はしたものの1回も参加していない。なぜならJavaC++も(参加できるほどには)使えないから。じゃあ覚えりゃいいじゃんと思うかもしれないが今はPythonの方を覚えたい気分だった。多分次はHaskell

その他

先ほどのstatから日本人上位者を探して片っ端からtwitter検索しフォローしまくってみるというのも手かもしれない。この辺は相手に迷惑かけない程度にしてください。


こんなえらそうなことを書いているが、私は去年1回戦で敗退した程度のぺーぺーなので、これを読んだ皆様には是非とも上位入賞して私を小馬鹿にしてほしい。
(本当は書くのためらっていたのだが、こういうの書く人誰もいなかったみたいだし書いてみた)

私の去年の参戦感想はこちら