Google Code Jam 2012 Round 2 参加記

GCJに参加しました。では結果をば

順位	得点	ペナルティ
631st	35	2:15:55
A-small	A-large	B-small	B-large	C-small	C-large	D-small	D-large
53:02	53:45	2:06:14 2WA	2:07:55	未提出	未提出	未提出	未提出

なんと！上位1000人に入ってしまったのでTシャツをゲットできました！ICPC以外のcompetitionでTシャツをゲットできたのは初めてで、嬉しいです！上位500に漏れてRound 3へは進めませんが最早そんな瑣末なことどーでもいいです（ぉ
ではいつもどおり、どんなことを考えていたか思考の変遷です

開始前

AtCoderのふか杯に出てウォーミングアップ的なことをやる
17:00に終了する
少し眠たい。GCJまでまだ時間あるし、仮眠を取ろう
寝る
起きる
21:00だ。まだもうちょい寝よう
寝る
起きる
23:10だ。
・・・あれ？GCJ始まってね？
急いでGCJのページ開く
「Compete Now!」（つまり始まってる）
ぎゃああああああああ寝過したあああああああ

開始

テンパる
問題数は4つなので、急いでGCJ用のテンプレートを4問分複製する
よし、落ち着け自分。まだ10数分しか経ってない（心臓バクバク
落ち着く
特に何も考えずA問題から読む

しょっぱなから問題長いな
じっくり読む
残念ながらあなたは空想のヒーローではない。ははぁ、そうでしょうねぇ
ツタの乗り継ぎ方がよく分からないまま読み終える
サンプルで理解を補足するか
ん？よくわかんない・・・
問題を読みなおそう
じーっと読み返しつつ、頭の中で主人公がツタを伝うところをイメージしつつ
なんとなく分かってきたぞ
改めてサンプル見る
答えが想像通りになる
ふむ、つまり、ツタiに届いたときに、ツタiがどこまで到達できるかを覚えておけばよさそうだな。
ツタiからツタjに届いたとき、ツタjからはxj + min(xj-xi, lj)の位置まで到達できる、っと。
O(N^2)くらいでできそうだ
書く
サンプル合う
出してしまおう
A-small Correct
やった！通ったぞ！このままlargeも出してしまえ
A-large submitted

この時点で1時間弱経過。でも順位的(確かこの時点で1000位前後でした)には10分出遅れたとはいえ、だいぶ盛り返したのではないか。
開始時点の焦りが0になる
次はどの問題がいいか・・・
Bのsmallは点が低いから取りやすいかもしれないな
Bを覗く
出力が浮動小数点なのを見つける
やめとこう、嫌な予感しかしない
Dはlargeの配点を見るに地獄問題だな
消去法でCを読むことにする

じっくり読む
え？自分で山の高さ決めなきゃならないの？
どーすんのこれ・・・？
あれこれ考えたが何も良いアイディアが出ずCを断念する

やばいやばい。もうBを読むしかない
Bを読む

W*Lの領域内に円を重なりも接することもなく並べろ、と
どーすんだこれ？
とりあえずサンプルを図に起こしてみる
ふむ・・・結構スペースには余裕があるなぁ
端っこから詰めていく方法で何とかならないかなぁ・・・
半径の降順でソートして、左端から詰めれるだけ一列に並べる
列の中で最も大きい半径をr、列のx座標をpxとする
その列に円を置けなくなったら、px + r + EPSだけ軸を右にずらす
次の列の最も大きい半径をr'とすると、軸をさらにr'だけ右にずらせば、1つ手前の円と重なることはない
こんなアルゴリズムでどうかしら？本当に空間が足りるかしら？
書いてみる
サンプルが合う
お、行けたか？出してしまおう
Incorrect!!
ありゃ、何がダメなんだ？
ソースとにらめっこする
あ！軸が右に動くときにy座標をリセットしてない！
直す
サンプル合う
出す
Incorrect!!
うおーー何故だーーー！？
にらめっこする
分からない
もしかして、空間外に配置しちゃってるのか？
デバッグ出力してみる
そんなことはなかった
え？まさか、円が重なったり接したりしてるの？
デバッグ出力する
ビンゴ、重なってる円がある
まさか、重ならないようなアルゴリズムになってるはずなのに・・・
ソースを見直す
あ！ここ、インデックスiじゃなくてjだろJK！
直す
デバッグ出力してみる
まだ重なってる
参ったなぁ、じゃあどういう順番で配置されているのか座標を出力してみるか
デバッグ出力してみる
座標見てもよくわかんない
ぱっと時計見る、残り30分くらいしかない
やばいやばい、もう順位も1400位くらいまで落っこちてる
あと少しで解けそうなのに、やばいやばい
ん？これ、円の交差判定のデバッグ間違えてね？
うあああ！間違いない！だって、2点間の距離ではiとjの円使ってるのに、半径の参照は別のidの円使ってるもの！
デバッグ出力をデバッグする（謎
円は重なってない！空間をはみ出すこともない！
提出だーーー
B-small Correct
キターーーー！
順位が900位台後半になる
あと30分弱でこの順位はきついかな・・・
こうなったらヤケクソだ。B-largeも出してしまおう。
こんな適当な貪欲が1000個も円があるB-largeに通用するとは思えないけど
いいや、出してしまおう
B-large Submitted

Bをsmall large出したので順位が600位台になる
B-largeの出力は目で確認した限りでは怪しいところは見つからなかった
ワンチャンあるかも・・・という淡いワクワク感を持つ
とにかくB-largeはコケることを前提にあと何か1つsmallを解いておきたいところ、残り時間は20分ほど
Cはムリゲー臭がしたのでDを読むことにしよう、それしかない

Dを読む
・・・
なるほど！無理ですね！

諦めてついったーへ戻る

終了

どきどきしながらスコアボードをF5する
！！
B-large通ってる！！！？？
奇跡だ！！

感想

最終順位を見たときに思わず
「いよっしゃあああああああああああああ」
と叫んでしまいました。
Tシャツ確定の嬉しさにしばらく興奮が冷めませんでした
思い付きのアルゴリズムで挑んだBですが、こういうことが起きるのでやっぱり何かしら書いてみるものだなと思いました。
それと、10分程度遅刻して参加しましたが、そんなときでも、あわてずに、落ち着いて取り組めば遅れを取り戻すことが可能ということが分かってよかったです