Google Coe Jam 2008 World Finals
http://code.google.com/intl/ja/codejam/
というわけで、参加してきました。
結果はSmall全部+A-Largeの36点で43位でした。
英語が全く駄目な私にとっては、無事に帰ってこれただけで奇跡なので、
あまり高望みはしますまい…。
サンフランシスコへ
コンテスト本番以外には特にイベントのないCode Jamは
着いた次の日の午前9時から開始というキツキツのスケジュールなのですが、
それは疲れそうだったので、私は一日前から現地入りしました。
終わった後もせっかくサンフランシスコまで行って何もせずにというのは
あんまりなので、一日延長しました。
これがなぜかフライトに有利に働いて、
ほかの人たちは韓国経由とかでやってきているところを
悠々と成田→サンフランシスコ直通便で行けました。
ひとりで海外に行くのは初めてだったのでとても不安でした。
なにしろ言葉が通じませんのでね。
しかし、必要に迫られて頑張ってみると、
案外コミュニケーションはとれるもので、
通じなくてどうしようもない、という状況はおきませんでした。
だいぶ経験値が上昇したような気がします。
クレジットカードを持ってなかったのも不安だったのですが、
これもまあ何とかなりました。
15万円持って行った現金は2万円+200ドルぐらいしか残りませんでしたので、
ちょっと何かがあったらまずかったかもしれません。
最初に日本で5万円両替して、500ドル弱手に入れたのですが、
ホテルに着いたらデポジットが700ドルいるとか言われて、
向こうでドルを調達したら5万円が400ドル弱にしかならなくて、悶絶しました。
私の1万円はどこかに消し飛んだようです。
Googleへ
さて、そんなわけで、レジストレーションとか立食パーティーみたいなのがあった翌日、
ついに本番となりました。
朝6時半ホテル出発の9時コンテストスタートです。
いきなり厳しいですが、日本時間じゃないので何とかなりました。
サンフランシスコの街を抜け、海岸沿いのハイウェイをひたすら南下していくと
どんどん何もないところへと向い、
その何もないところの一角にGoogleはありました。
日本でいうと京阪奈みたいなもんなのかなあと思いました。
Google本社は、思っていたのとだいぶ違って、
きっとそれは日本Googleを先に見ていたからだと思うのですが、
広い敷地にあまり高くない建物がたくさん、
さしずめ大学のキャンパスのようでありました。
食べるところがたくさんあって、そこらじゅうに自由に飲める飲み物が設置されていて、
中庭にはビーチバレーのコートから恐竜の化石までありました。
中国か韓国かのテレビがインタビューに来ていました。
軽い気持ちでOKOKとか言ってしまったのですが、
何聞いてきているか全然わからないし、
終始しどろもどろの対応で(自分が)ひどかったです。
解答は日本語でOKですよ、みたいなことを言われたので
日本語で答えておきましたが、たぶんインタビュアーの人は
日本語わかっていないので、かみ合わない妙な雰囲気のまま終了。
コンテストの会場は、食堂の横のスペースに設営されていました。
たぶん食べるところだったのだと思うのですが、
そんなオープンなスペースでコンテストは始まりました。
本番
持参した日本語キーボードを取り付けたり、GNOMEの設定を変えたり、
テンプレートがコンパイルできることを確認したりして、開始を待ちました。
画面上にカウントダウンが表示され、それが00:00になってコンテストは開始しました。
開始しても会場はシーンと静まり返っており、
あれ、これ始ってるの？と不安になりましたが、
Enter Contestというボタンを押すと問題が見れたので、
確かに始まっているのだということがわかりました。
(問題はこちらを参照)
http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamFtchALEghjb250ZXN0cxjRzBQM
この日の戦略はノープランでした。
何をどうしたらいいか何も考えていなかったので、
とりあえずAを読みました。
読み始めたは良いものの、全然頭に入ってこなくて参りました。
英語が難しいのか、問題のシチュエーションが現実離れしているから
想像で補うことができないからか、とても解読に苦労して、
やはり例によって例の如く、読んでる最中にサブミットがされ始めました。
10分ぐらい経ってようやくなんとかサンプルと整合性のとれる理解が得られたのですが、
それでもそれが合っているか分からなかったので、
英語の理解を確信にするためにとりあえずSmallのコードを書くことにしました。
コードは数分で書き終わり、サブミットするとCorrectと帰ってきました。
よかった。理解は間違っていなかった。
Largeの解法は思いつかなかったので解く問題をBに変更。
Bも英文が全然頭に入ってこなくて参りました。
これもシチュエーションが不自然すぎるのです。
なんでネズミ捕りなのか意味がわかりません。
これもとりあえずSmallを通すことにしました。
普通に深さ優先的にペイントして終了。
Largeは計算しないとできなさそうだなあと思ったのでCに移動。
Cは問題文が素直で助かりました。
しかしLargeの解法はまるで思いつかなかったので
とりあえず全部調べろといわんばかりのSmallを適当に通しておきました。
この辺までは一問15分ペース
残るDとEは問題が長かったので、とりあえずDから手をつけることに。
Smallの解法も自明ではないように思えましたが、
少し考えると、とりあえずもう一つの森まで最短でつないで、
あとはBFSのminをとればいいように思えたのでそれを実装。
しかしなんだかコードがすっきりしなくて、
どろどろしてきたので、一旦Eにスイッチ。
Eもシチュエーションが現実離れしすぎていましたが、
解読は普通に終わり、Smallもできそうな感じでした。
15*2^15*2^15*15ぐらいの計算量だったので、不安もありましたが
ぐずぐずもしていられないので、実装を始めました。
コード自体はすぐにできて、サブミットしようとしたのですが、
テストケースを持ってきて、実行させてみると全然間に合わない。
これはやばいかなと思いつつ、
スコアの計算などをビットごとにループを回していた部分をテーブル引きに変えたり、
生成したパターンが有効かどうかのチェックもテーブル引きに変えたりして
15の係数を一つはずして、サンプルを再入力。
4スレッド並列で3分ぐらいで終わったので、行けるだろう、として、
二つ目のサンプルをサブミット、やっとこさSmallが通る。
かなり時間を消耗してしまいました。
この辺で残り一時間ぐらい。圧倒的に時間が足りない。
一通り問題を見たのでDに戻る。
ちょっとコードから離れていたので、見通しが良くなっていました。
するするとかけて、するすると終了。
さっき書いてた時に感じたのはなんだったんだろう。
そして残り45分ぐらい。
Smallが終わって、次に何をやるか。
といってももう全然時間がないので絞らないといけません。
解けそうなのはDのLarge。
Smallと同じような感じで、
森を全部spanning treeつないで、それから全森からのBFSのminでいいような気がしたのですが、
なんだかすっきり書く方法が思いつかず、17点というのも
本当にこんなんでいいのかという気にさせてくれて、やっぱりDはやめることに。
あと解けそうなのはAのLargeとBのLargeか。
AのLargeはかなりたくさんの人が解いていたので、
これはやるべきだろう、ということでAを考え始めました。
ジュースをミックスする割合を決めて、それぞれについてチェックしたらO(n^3)か。
これはn=5000には大きすぎる。
割合を決めるのにO(n^2)、あとは決めた時のカウントがO(1)かO(logn)かで
できれば何とかなると考えて、10分ほどうんうん唸っていると、
fenwick treeでできるんじゃないか、と気付きました。
分かったらコードはすぐできて、
しかし、万が一にもTLEなどあってはならないので、
手元で大きなケースを作って、
それでも十分に速いことを確認して石橋をたたきながらLargeをサブミット。
残りは15分。もう解法が今すぐに思いついても一問も
書けないような気はしていたのですが、
一番可能性の高そうなBを考えることにしました。
しかし考えてもいい案は浮かばず。
Dがもしかしたらすっきりいけるのかなあと思いながらDを眺めてみるも
これまた何も浮かばず。
そんなこんなで、ぐだぐだしながらのこり15分を過ごしました。
終わる時もあっさりと終了。カウントダウンぐらいあってもよかったんじゃなかろうか。
終了後
終わって一息ついていると、
今度は日本の記者がインタビューしたいらしいとのことなので、
これまたOKOKとか言っているとなんか別室に連れていかれて
そこでインタビューを受けました。
今度は日本人の方だったので、普通に日本語で対応しました。
外国でこう日本語で受け答えするのって、
ちょっと不思議な感じで、ちょっと楽しかったです。
それからご飯を食べたり日本人で集まって解法を言い合ったりしました。
Googleの食堂はいろいろな国の料理があって、なかなかおいしかったです。
もちろん和食もあって、と言っても寿司なのですが、
せっかくなのでカリフォルニアの寿司も食べておくことにしました。
目の前でサーモンの握りを握ってくれて結構本格的なんだなあと思いました。
味も結構ちゃんとしていました。
どうでもいいのですが、サンフランシスコの街には妙に寿司屋が多くて、
3分歩けば必ず見つかるほどです。
日本でもそんなにないと思うのですが、
よほどサンフランシスカンは寿司が好きなのでしょうか。
食事が終って、社内を見学したり、
Googleの技術の説明を聞いたりしました。
イベントがほとんどないのに、そういうアピールはするのだなあと思いました。
途中、Java Puzzlersという本？からJavaの奇妙なふるまいについての話がありました。
私はJavaはほとんど使わないので、そんな重箱の隅仕様は知っているはずもなく、
なんでアメリカくんだりまで行ってJavaの勉強をせねばならないのかなあ、と思いました。
それからホテルに帰って、表彰式でした。
アルコールが出たので、もらいに行くとIDを要求されました。
まあなんというか、年齢制限のあるものなのだからこれぐらいは当然なのか。
ディナーを食べながら下のほうから順に発表されていきます。
とりあえず97位から51位までには入っていなくてホッとしました。
AのLargeは通っていたっぽい。
しかし、次の50位から26位で名前が出て来て
やっぱりこんなもんだよなあという感じでした。
1位はACRush氏でした。鉄板過ぎる。
89点というのが自分との如何ともし難い距離を感じさせます。
久しぶりに、悔しいという気持ちが沸いてきました。
勝ちたい、終わってからだというのに。
来年ももしあればもっと自分を鍛えて行きたいと思いました。
観光
一日延泊して観光してきました。
サンフランシスコは坂が多い街です。
東京もたいがい凸凹した街だなあと思っていたのですが、
比べ物にならないぐらい坂だらけです。
とりあえず、坂道をがんばって歩いて日本人街に行ってみました。
あまりにも日本でびっくり。
紀伊国屋書店があったのですが、内装から置いてある本までどうみても日本で、
とても奇妙な感覚でした。
それから中華街とかを見て、
名物のケーブルカーに乗りフィッシャーマンズワーフに向かいました。
ガイドブックに載ってた、フィッシャーマンズワーフで自転車を借りて、
ゴールデンゲートブリッジを自転車で渡る、というやつをやりました。
英語がなかなか聞き取れなくて、自転車を借りるのに一苦労。
クレジットカード持ってないの？持ってないけどそこを何とか貸してくれ。
なんか店長みたいな人に話が行って、クレジットカードは？ないです。
うーん。とか何とか話が進んで、
じゃあ300ドル出せという話になったのですが、
所持金が260ドルしかない。
ちょっとそんなにお金ないです、と言ったら、
じゃあそれでいいやということになって、全財産と引き換えに
自転車を借りることができました。
閉店までに帰ってこなかったらお金返せない、
しかも閉店まで2時間ぐらいしかないという状況だったのですが、
がんばって自転車を漕いで、何とか間に合いました。
アメリカまで来てこんな危ない橋を渡る必要もなかったかなあ。
自転車は結構良くて、なんとGPS付きでした。
橋は結構高い所にかかってて、そこまで登るのにも一苦労。
橋からの眺めはなかなか爽快でした。
良い経験ができました。
そのあとはフィッシャーマンズワーフで買い物とかして、
書店でマンガとか買ってみたりして、ホテルに帰りました。
