Google Code Jam 2006 Qualification Round

昨晩 Google Code Jam に参加しました。
去年はRound 2の低得点問題を落として
Championship Round にいけなかったのですが、今年はいかに。

http://fxp.hp.infoseek.co.jp/img/gcj_2006_qr.png

Qualification Round で落ちるわけにはいかないので、
かなり緊張していたのですが、
ここで200位に入っていれば次にいけるのでしょうか。
ひとまずはシステムテストに落ちなくてほっとしています。

今年はC++,Java,C#,VBに加えてPythonが使えるようになったのですが、
Phythonは全く使い慣れていないので、今年もC++で行くことにしました。
C++,Java,C#,VBと、はっきり言って何も変わらない言語ばかり
(JavaとC#なんて本当に何も変わらないし…)
ムダに4つもあったところから考えると
Pythonの追加は非常に画期的で、
一つだけ明らかに記述力が高いという状況になってしまっていますが、
そこはGoogleなので、ワザとやっているとしか思えません。
そんな言語を使えないのは残念ではあるのですが、
私はPythonを常用していないしする気もないので、
致し方ないところ。Googleとは相容れません。

というわけで問題ですが、
私はSet 3に割り当てられておりました。
問題は250点のと750点のとの2問で、時間は一時間です。

250点問題はサッカーの審判のカードの出し間違いを検出するという問題。
審判は同じ選手にイエローカード二枚目を出したら、
即座に同じ選手にレッドカードを出さないといけないらしいのですが、
その出し忘れがあれば、その一番早い時刻を求めろというもの。
この問題の一番の難点は、英語が長いということ。
あまりにも長い…。
途中で心が折れそうになりましたが、
なんとか8分ぐらいかかって問題を理解することが出来ました。
まぁ、作業問題なので、コードは書くだけなのですが、
条件の見落としが無いかとっても不安。
書きあがってテストをしようと思ったら、なんと、接続が切れました。
この一刻を争う時になんで…と思いながらもなんとか冷静を保って、
一旦問題を閉じて安静にしていると2分後ぐらいに復帰しました。
それからテストをして、全部通っていることを確認して、
さらに自分でいくつかテストケースを作って、
問題ないことを確認してからサブミット。
ここで開始15分ぐらいでした。

750点問題は正方行列Aに対して、
��(A[1][p[1] ]*A[2][p[2] ]*...*A[n][p[n] ]) (pは[1,..,n]の並べ替え全て)
の下四桁を求めるというもの。
行列のサイズは16×16まで。
この問題は英文が短くて非常に助かりました。
問題は2分ぐらいで読めて、解き方も5分ぐらい考えていたら分かりました。
16!*16は時間的に無理ですが、
普通に再帰的に解くと考えても、
再帰中の状態数が、16*2^16ほどにしかならないので、
キャッシュしてやれば計算は一瞬で終わります。
TopCoderに何度か参加したことがありますが、
2^Xでキャッシュすれば解けるというのは
ここでは結構頻出ですね。
コードはそんなに時間もかからず完成したのですが、
またもここで接続が切れてしまいました。
なんじゃこりゃー？と思いつつも再度一旦問題を閉じてじっとしていると
何分かして復帰。
テストをすると見事にバグっていて、これがなかなかとれない。
coutデバッグをしばらくしてようやくバグを発見。
十分にテストをして提出。
残り18分ぐらいでした。

提出したコードを貼っておきます。
http://fxp.hp.infoseek.co.jp/oth/gcj_2006_qr_250.cpp
http://fxp.hp.infoseek.co.jp/oth/gcj_2006_qr_750.cpp

しかしまぁ、なんといいますか、これはちょっと不本意な感じですね。
二問目に時間がかかりすぎました。
こんな単純なコードにバグを入れるなんて、
私も耄碌したものですね。
このままでは次の次とか次の次の次とかに進むのが
厳しいかもしれないので、もう少し何とかしたいところです。