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

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

TCCC06 Qualification Round 1

TopCoderから送られてくるメールが出ろ出ろとうるさいので、
2006 TopCoder Collegiate Challengeなるものにも出てみました。
なんだかルールの記述がやたらに長いのであんまり読めてなくて
参加資格があるのかどうかも良く分かっていませんが…。
レートが高い人はQualification Round免除、
他の人はいずれかのQualification Roundで勝ち抜ければ良い、でOKなのでしょうか。
なんだか、Qualification Roundはまだ2回あって、
参加登録もまだ受け付けているみたいなので、興味のある方はどうぞ。
私はレートが低いのでQualification Roundから参加しました。

http://fxp.hp.infoseek.co.jp/img/tccc_2006_qr1.png
普通のTopCoderのルールと同じで、3問75分、チャレンジありでした。
上位450位が次に進出なのに、参加者が700人弱しかいなかった…。

250点問題
http://www.topcoder.com/stat?c=problem_statement&pm=6698&rd=10093
よく考えると、ソートして、前半を加算、後半を減算すれば良いだけ。
サイズが非常に小さいので、ナイーブに再帰的にとか書いても良いけど、
ナイーブに書かないほうが楽なんではないでしょうか。

500点問題
http://www.topcoder.com/stat?c=problem_statement&pm=6505&rd=10093
男女交互に身長順に並べよ、解が複数あるならレキシコ順、という問題か。
男女それぞれ分離してソートして、インターリーブして(高々二通りの方法で)、
それが条件を満たしているか調べるだけのような感じ。
レキシコグラフィカルというのが、辞書順なのか、アスキー順でいいのか
良く分からなかったので、びくびくしつつも面倒なのでアスキー順で提出。

1000点問題
http://www.topcoder.com/stat?c=problem_statement&pm=6667&rd=10093
15パズルの円筒版のような問題ですが、
有効なヒューリスティック関数がわからないので、IDA*で解くのは厳しそう。
そもそもIDA*は計算量の上限が見積もりづらいですが…。
イラストに反してサイズが3*4までなので、
幅優先で解いてしまってよいと思うのですが
(状態数が40万ぐらいにしかならないので)
あとでいろいろ試したのですが、この問題はそれでも厳しいです。
最後のサンプルが手元で6秒ぐらいで解けるのが精一杯というところ。
本番中はなんか勘違いして単にキャッシュつき深さ優先探索をしてしまって、
どう考えてもスタックがあふれるような状態で提出してしまい、
当然のごとく一瞬でチャレンジされてしまいました。
いずれにせよ、これはかなり難しい問題では無いでしょうか。
高レートの人が参加していないとはいえ、一人も正解者がいませんでした。

出したコードは
http://www.topcoder.com/stat?c=problem_solution&rm=249604&rd=10093&pm=6698&cr=22627322
http://www.topcoder.com/stat?c=problem_solution&rm=249604&rd=10093&pm=6505&cr=22627322
この辺から見られるようです。
こっちも出来るだけ進めるように頑張ってみますか…。