Google Code Jam 2010 - Round 1A

GCJのRound1（前回は所謂Round0ｗ）。Round1にはA,B,Cの３つがあって、そのうちどれかの上位1000人に入ればラウンド２進出。仮にAがダメでもB、BがダメでもCに参加でき、通過した以降の試合への参加はできない。まー要するに3000人がラウンド２に行けると。

Dashboard - Round 1A 2010 - Google Code Jam

結果は 612位（スコア:39）でした。あまり良い成績ではなかったけど、普段かなり強い人もラージを落としたりしていたので、やや難しめのセットだったのかもですね。

A. Rotate

『ぷよぷよ』みたいな具合で青と赤のブロックが積まれてあって、その勝敗判定の問題。ただしちょっとしたズルが可能で、盤面を一度だけ時計回りに90度回転できます。
これはやるだけ問題。起きてすぐの開始だったので、オーダー計算にナイーブになってしまい、ちょっとDPチックな実装を一時間ほど頑張ってしまいましたｗ。普通にループをブン回しても問題なかったみたい。。。小さな工夫としては、90度回転後の重力操作は右寄せ操作と等価なので、右下を原点にして実装したほうが楽ってくらいですかね。
ところで問題文中に“in a row（連続で）”っていう語が出てきましたが、このフレーズを知らない人は“一つの列に”って勘違いするんじゃないかと思った。俺はDUOで覚えていたんだけど、それでもどっちの意味か分からなくて、それぞれの意味で並行して読んでました。できれば“sequentially”とか別に語を使って欲しかったなぁ。

B. Make it Smooth

ダイナミックレンジが8ビットの一次元信号があって、これを滑らかな信号（差分信号の最大振幅がM以下）にしたい。挿入・削除・増減の３つの操作が可能で、その最低コストを答える問題。
もう見た瞬間に、DPの有名問題である編集距離とかそういうのだろうと思ったけど、編集距離の解法をよく知らないので無視。解いてません。

C. Number Game

二人でやる数字のゲームです。先手が必勝可能な問題パターンを数えろと。詳しくは本家サイトを参照してください。
完全にオーダー計算を勘違いして二重ループの存在を失念。全力でSmall向けの実装に取り組んでしまいました。Largeを実行して気づく始末（orz）。そしてTE（以降挑戦不可）。残念。

bool search(int a,int b)
{
    if(a==b) return false;
    
    int r=a%b;
    if(r==0) return true;
    if(r+b<a) return true;
    return !search(b,r);
}

↑が実装した再帰関数と等価な（コンテスト後に整理して書き直した）コードなんですが、これを実時間内に100万×100万回も呼び出す方法がどうしても解けませんでした。メモ化にはメモリが足りないし（部分的メモ化も考えたけど実装が間に合わなそうだったし）、枝刈りもイマイチいい感じのルールを見つけれず。。。
解説やら上位のソースを読んだところでは、解析的に答えが求めれるみたいです。その方程式が「x^2+x+1=0」すなわち「x=(黄金比)」であり、これを境界として返値が反転するらしいです。実際に、上記再帰関数の返値をニ次元マップで表示すると、綺麗に境界線（直線）らしきものが見えました。せめてこれに気づいてれば・・・いや、やっぱ時間内には気づかんわ（笑）。みんな頭良すぎです。
公式解説では「ゲームの流れがフィボナッチ数→黄金比に帰着できる」みたいなことが書かれてました。それと別のアプローチとして、境界線がリニアだと分かったんなら係数を何とかして（二分探索とか？）求めればよいというコメント。さすが、Google社員。
まーとにかく、解き方が多数あってコンテスト後も楽しませてもらったので超良問ですね。

むすび

やはり現役コンテスタント時代と比べると実装速度が遅くなった感じですが、その代わりに英語力が向上して以前より問題読むのが早くなってるし自信を持って実装開始している感じがします（笑）。よって結局プラマイ０ってところかなｗ。