Google Code Jam 2011 - Qualification Round

昨年に続き、２回目の参加でごわす。25点以上取れればRound1に進めます。だいぶ時間かかったけど、今年はなんとかScore:100(Rank:1269)で通過できました(^_^)v。問題等はこちら。

http://code.google.com/codejam/contest/dashboard?c=975485#

A. Bot Trust

正しくシミュレートするだけ。オーダーの罠とかもなし。スイッチは指定の順番通りに押さなきゃいけないので、片方のロボットは必要であれば待機しておく必要がある。相方が頑張ってる時の時間を蓄積しておいて、自分の番になったら、そこからできるだけ時間を引き出す、みたいな感じの実装にした。

B. Magicka

バグでドハマリした。文字列処理は苦手でごわす。問題自体はやるだけ。この手の問題は英語を正しく理解できるかのほうが不安。。。

C. Candy Splitting

ヒドイ兄と馬鹿な弟の問題。弟の計算法はまさにXOR。要するに、「両者のキャンディー値のXOR和（便宜上そう呼ぶ）が一致」するという条件のもとで、「兄のキャンディー値の総和が最大」となるときのその最大値を答える問題。先の条件が一切成り立たない場合は弟号泣。
最初は「Largeサイズは素直に解けないけど・・・」と思いつつ探索かなーと突撃。途中でもっと賢い方法に路線変更。XORの性質を把握することがポイントかな。例えば、 $\oplus$ をXOR演算子として、兄のキャンディー値をa,b、弟のキャンディー値をc,dとすると、上記条件は $a \oplus b = c \oplus d$ と表せる。で、XORの性質をよく考えてみると、任意の変数は別に符号反転的なものもなしに移項でき、その条件も当然成り立ったまま。なので、上記条件が満たされるかどうかは、実はキャンディー値が与えられた段階で既に決まっているわけである。んでんで、兄のを最大にしたいわけだから、究極的には $a \oplus b \oplus c \oplus d = 0$ なわけだけど極悪非道すぎるので（うそっ。サンプルケースが通らないのでｗ）、弟に一番安いキャンディをあげときゃいい、ということになる。
ちょっとした洞察力が求められる面白い問題でした。XORの性質を深く考えるキッカケになったかな。

D. GoroSort

オレ的ベストプロブレム。最初、間違いを送信したけどなんとか挽回できた。
確率論の観点から平均打回数を求めよ、っていう感じの問題。最初そこまで深く考えておらず、「2個交換なら2打（1/2）、3個交換なら3!=6打（1/6）必要だから、実は2個交換を繰り返すのがベストなんじゃないか〜」ってな具合に想像して、そして鮮やかに Incorrect くらいました。だってサンプル通ったんだもん。。。
結局状態遷移の確率はもっと正しく求める必要があることを知り、小さなパターンから帰納的に類推。対象が0個なら0打（交換必要なし）。対象が1個のケースは問題の性質上存在しない。2個なら問題文にあるように2打。3個なら3!=6パターンすべてを列挙して求める。具体的には、3つ全部が整列する確率（1/6）、2つが整列する確率（0/6）、1つが整列する確率（3/6）、全く整列しない確率（2/6）を求める。n個の整列に必要な平均打回数を $x_n$ とすると
$x_3=1+(1/6)x_0+(3/6)x_2+(2/6)x_3$
と書ける。 $x_0 = 0, x_2 = 2$ を使って $x_3$ を解くと $x_3 = 3$ 。同じように4個の場合もやってみると・・・あれれ？？・・・ $x_4 = 4$ になっちゃったよ？？。ってことで、もしかして $x_n = n$ なんじゃないかと半信半疑ながらコーディング再開。初期位置が正しい位置でない数をカウントするだけなので、当然超簡単。で、見事Correct!。独立試行でないと面白いふるまいするのねぇ。

むすび

無事に全問正解できたので、２週間後のRound1、頑張ります（昨年はRound2で敗退）。もうちょっと速く解けるようにならんと。。。