先日 Google Code Jam 2010 の Qualification Round で撃沈したのでそのことを書こうと思うんですが、その前に去年の GCJ 2009 の書きかけメモがあったので、これを先にまとめておこうかと。（本当は GCJ 2010 前にあげて「みんなも参加しようよ」的な流れにしたかったんですけどね・・・。）
長くなるので、3 回くらいに分けて書く予定で・・・まずは Round2 で果てるまでの流れを書いておきます。なお、2009 年に書いた内容がベースですので、感想その他は当時のものです。
Google Code Jam って？
Google がだいたい毎年やってるプログラミングコンテスト。
私が今まで参加したのは、2005（使用言語: C#）、India 2006（使用言語: Java）、2006（使用言語: Python）。
2008 年からデータファイルをダウンロード→制限時間内に出力ファイルを作成してアップロードという流れになっているので、言語は何でもいいらしい。プログラミングのスキルだけじゃなくて、言語選択のセンスや手際のよさも必要ってことじゃん。燃える。なんで去年気付かなかったかなぁ。
2006 年までは不慣れな言語ばかり使ってて、「こういう場合はどう書くんだろう？」と手が止まることが多かったけど、今回はせっかくなので一番手になじんでる Perl でいくことに。PHP もそこそこ慣れてるけど、ちょっと配列データをいじりたいときに array_map(create_function(...), ...) みたいに書くのは嫌だし、PHP 5.3 はまだ慣れてないし。
去年の問題解いてみたり
Qualification Round の前に Practice Problems を 2 問ばかり、Round1A の前に Round 1A の問題を、Round2 の前に Round2 の問題を解いたりしました。
印象的だった部分だけ書いておきます。
Round 1A C. Numbers
この問題。計算式自体は簡単なんだけど、浮動小数点の精度の問題で、単純な解き方だと Small すら通過できないというもの。
高精度の計算が行える言語を探してたら、
というのに行き当たりまして。50 桁程度まで保証できるようなので、Small dataset（2 <= n <= 30）までならこのサイトで・・・
for (j = 0; j <= n; j = j + 1) {
print(j);
print((3 + sqrt(5)) ^ j);
println(mod((3 + sqrt(5)) ^ j, 1000));
}こんな感じで解けちゃいますね。桁数を 14 に変更して実行（※ふつうの言語の精度がだいたいこんなもの）すると、n = 19 までしか精度保証されていないのがわかります。
他の環境では Mathematica が計算精度を指定できるらしい（参考: 数値の精度 - Wolfram Mathematica 7 Documentation）ので、似たような機能でフリーの Maxima を試したんだけど、精度指定の方法がよくわからなかった。
まだちゃんと読んでないですが、数学的に解けばこんなことしなくてもいいらしいです。
2008 Round 2 1. Cheating a Boolean Tree
枝切りしたあと全組み合わせを実行する形で解いたけど、その解き方だと組み合わせ爆発して計算時間がとんでもないことになってしまった。ここも分割＆統治っぽいことアルゴリズムで自然に解けないとダメですね。
Qualification Round
開催期間が 24 時間あるので、この間に 30pt 以上稼げば OK とのこと。
2 時間くらいを目標にやってたけど、まず B を解いて、A を手抜きで解いて、その後 C の small を解いて。C の large は実行時間切れ。76pt なのでまあ通過と。さらっと書いてるけど、Qualification Round 通過したのははじめてなので結構嬉しい。
Round1A
Round1 は A、B、C の 3 回に分けて実施されるけど、それぞれで 1000 位以内に入れば通過と。で、A で通過した人は B、C には参加できない。
で、その Round1A。C を考えてたけどどうも無理そうで、A に乗り換えたけど、large の計算が終わらず。その後 B を解いてたけど時間切れ。9pt で 1755 位なので通過はできず。
A の large が計算が終わらない件は詳しく書きたいところなので、余裕あれば別項で。
Round1B
A をもったいない解き方して、B もふつうに解いたくらいで時間切れ。それでも 56pt で 807 位なので Round 1 は通過と。
もったいない解き方というのは、データの解析処理を
while (not $t =~ /\G\z/gc) { if ($t =~ /\G\s+/gc) { next; } elsif ($t =~ /\G\(/gc) { # 以下分岐が続く
こんな感じで簡易パーサ作って解いてしまったこと。これじゃ C 言語で解くのと大差ないし。
LL らしく、
$t =~ s{\(}{[}g; $t =~ s{\)}{],}g; $t =~ s{([\w.]+)}{'$1',}g; my $data = eval $t;
こんな感じで変換かけて、スクリプトエンジン側に処理させるべきだったなぁ。なぜか「連想配列で持たなきゃー」と思ってしまったんだよねこのときは。
ちなみに B も C++ なら next_permutation() とかいう関数があるので一発らしい。Perl の Math::Combinatorics にある同名の処理と違って、与えられた文字の次の順列を拾えるらしい。こういう言語ごとの特徴を活かせるようになるといいんだけど。
Round2
500 位以内に入れば通過＆Tシャツもらえるとのこと。
A、B、C、D すべてさらっと眺めてみたけど、すぐにアルゴリズムを思いつくものがない。D をとりあえず考えてみる・・・けどいける気がしない。
アルゴリズム思いついてないけど、A をやってみる。解きながら「これでいけるんじゃね？」というのを思いついたので、それで submit。どうやら OK らしい。
そういうノリで C も解けるかも？とやってみたけど、incorrect。そりゃそうか。
あとは力技で small くらいなら解けそうな B をガリガリと解いてたけど、時間切れ。
後でよく考えたら、D の small は 1 ≦ N ≦ 3 だから全組み合わせで解けばいいだけだったし、C やらずにこっち解いてればよかったなあ。どっちにしろ B が間に合わなかった気がするけど。
まとめると
こんな戦績でした。かなり汚いコードだからちょっと恥ずかしいけど。
-
-
- -
-
ということで、次回は細かい Tips なんかの話を。
