Google Code Jam Round 2

Program

負けた…
http://fxp.infoseek.ne.jp/img/gcj_2005_r2.png

        • -

今回の問題は300点、450点、1000点の3つ。
時間は前と同じ75分。


300点問題は、
迷路の中を複数のプレイヤーが陣形を崩さないように探索するとき、
誰か一人がゴールにたどり着くまでの最短距離を求めよ、というもの。
普通に幅優先で終わりかと思われるが、
いろいろとめんどくさい。とてもめんどくさい。
ついに300点問題でこの難易度になったか、としみじみ思う。
35分もかかってSubmit。


この時点で3問解くのをあきらめる。
400点問題は

function hash(bits)
  set key = 0
  prepend '0' to bits
  for( i = 1 to lengthof(bits)-1 )
    if(bits[i-1]=='0' and bits[i] == '0') key = (key * mults[0] + adds[0]) % size
    if(bits[i-1]=='0' and bits[i] == '1') key = (key * mults[1] + adds[1]) % size
    if(bits[i-1]=='1' and bits[i] == '0') key = (key * mults[2] + adds[2]) % size
    if(bits[i-1]=='1' and bits[i] == '1') key = (key * mults[3] + adds[3]) % size
  end
  return key
end

というアルゴリズムに基づきハッシュを生成する。
nビット以下のすべてのデータに対してハッシュを生成したとき、
もっとも多く生成されたハッシュの生成回数を求める、というもの。
ちなみに、ビット数は50まで、sizeは10000まで。
これは、nビットまでの頻度表（と直前のビット）があれば
n+1ビットに対するものが求まるので、DPできる。
これは思いついたら割とすぐ実装できて、
開始1時間ほどでSubmit。


残り時間が少ないので1000点問題は解ける気がしなかったが、
一応少しは考えてみた。
p1 .. pn が与えられたとき、
k1^p1, .. , kn^pn (k>=2, i!=j => ki!=kj)
をすべて約数に持つ最小の整数を求めよ、というもの。
たとえば、{2,2,2} なら 答えは 36。
（2^2, 3^2, 6^2 と選んだときが最小）
制約条件は、n=10までだということと、答えはlong longに収まるということ。
時間まで考えるも、うまい方法はさっぱり思いつかず。
DFSで間に合っちゃうのかなぁ、とか思ったり思わなかったり。


というわけで、Coding Phaseが終了。
続いてChallenge Phase。
ほかの人のコードを見てみるが…。
ぜんぜん間違いが見つからない。
さすがにRound2ともなるとあからさまな間違いをやらかす人はいないのか。
それから大体全員分のコードを見るも、結局おかしいところは見つからず。


程なくしてシステムテスト。
システムテスト前の順位が120位ぐらいだったので、
上位が落ちればどうなのかなぁ、といったところ。
さすがに参加者が少ないので、あっという間にシステムテストが終わり、結果が出た。
1000点問題そもそもSubmitしている人が20人ぐらいしかいなかったが、
最終的に通ってる人は2人しかいなかった。
やっぱりとんでもなく難しい問題だったんだなぁ。
で、私はというと…。300点が落ちてた…。
どんな入力で落ちてたかというと、
{".."}というような、プレイヤーもゴールもないような入力だった。
こういう場合は放っておいてもうまくいくと思い込んでいたが、
どうもだめだったようだ。サブミットする前に
プレイヤーがいなければはじいておこうかとも思ったのだが、
プレイヤーがなくて、ゴールだけあるやつがうまくいっていたので、
大丈夫なのかなぁと思い込んでしまっていた。
ああ、だめだ。


しかし、300点問題が通っていれば得点は430ほどになり、
大体90位で通過していたことになる。
惜しかった。かなり悔しい。
とりあえず今回の教訓は、フェイルセーフに実装しろ、ということだ。
今回はプレイヤーがないときにはじいていれば通っていたんだから。