読者です 読者をやめる 読者になる 読者になる

本履歴

購入した古本の履歴と時々プログラミング

GCJ 2011

Google Code Jam 2011 Qualification Round通りました。当日会社があったけど、もちろん休みましたとさ。

結果

2011→http://www.go-hero.net/jam/11/name/uru
(2010→http://www.go-hero.net/jam/10/name/uru
初めての予選全問正解。問題が例年に比べて簡単の気もするけど、まじうれしい。

環境

言語はRubyメインで。今年はnarrayという高速配列とmemoize(これは去年から)という関数の結果をメモ化するライブラリを利用する。
サーバ側で動かすコンテストでは利用できないけれど、自分の環境で動かせるGCJならでは。
あと、Free PascalGolangも使う。

Qualification Round 2011

朝8時に起きて、問題をざっと読む。D以外簡単そう。Largeの数字が全然でかくないので。

A. Bot Trust

片方のロボットがボタンを押すため移動する時間+ボタンを押す時間(1sec)の間に、
もう片方のロボットを、次の目的のボタンまで移動させる(できない場合は、途中まで)ようにすればOK。
ちょっとはまったけど、解けた。Pascal使った。

B. Magicka

Rubyで。最初わからなかったが、問題文を2回読んでようやく内容を理解できた。
文字をinvokeするたびに、

  1. その文字とelement list最終文字がcombineリストにあるか? あれば結合して次をinvoke
  2. その文字がopposed 文字か? そうなら、element listに相方は載っているかチェックし、あれば全消去

という方針でsmall解けた。basic elementが8文字とか、結合したらelement以外になるとかで速くできそうだったが
Data setの数字が小さいので、大丈夫そう→N=10000でテストしてOKだったのでそのままsubmit。

C. Candy Splitting

二つの集合に分解できるかは、xorをとって0になるかで判断するのはすぐわかる。ニムみたいだね。
最大にするにはどうしたらいいか、空集合を渡せるといいのだけど、とかいろいろ考えていたら
最小値を一つあげればいいじゃん、と気づく。
ここまで紙上で考えて、あとはGolangで解いた。

D. GoroSort

パッと見、CodeChefの今年2月の問題(http://www.codechef.com/FEB11/problems/BOGOSORT/)に似てるなあと感じる。
有理数出力でなく小数だから簡単かと思ったけど、1000!((1000/5+1000/25+1000/125+1000/625)桁!!(5/13訂正 ←って0の数やん。まあ、大きいってことで・・)が出てくるので、誤差がどうしても出てきそう。
ハテどうしたものかと思案しまくり。
N=4のテストケースがヒントで、与えられた置換を巡回置換の積にし、それぞれの平均回数を足せばOKと気づくも(これで回数減らせるとは・・・ググるさんの優しさに感謝する)
やはりBOGOSORTの場合に帰着される。でも、BOGOSORTの問題文をよく読むと両端からしか固定できないので今回とちょっと違うなあ・・・
結局、誤差が出てもいいように平均回数を10000000倍して整数で全て計算していき、最後に小数フォーマットに落とすことで誤差をなくすこととし、Rubyでコーディング開始。
ここは、DerangementなどBOGOSORTに挑んだ時の知識が役に立った。すごいよ、CodeChef!!1
できあがってN=1000まで出力させたところ全て整数が出てきて、自分のプログラムがバグっていると知りかなりショック。でも間違ってる箇所が分からない。
冷静になって紙上で計算したところ、今度はなぜか汚い分数になり、プログラムとオレどちらを信じればいいのやら。ググるさんは小数6桁まで出せと仰っているし。
トップの人がすぐに解けていることなどもあり、そんな難しいことはないとも思い始める。
だんだん飽きてきたので、Nが小さい場合にシミュレーションすることにし、最終的に整数になることを確認出来た!
安心して、puts(ans+".000000")をsubmit。