Day 1 - 開始直前

Google Code Jam Round 2 に出る 0完冷えすぎる風呂に入って寝る

起床絶起やんけ朝食を食べて向かう

到着優秀なので集合時間に間に合う

地下着わいわい提出は1人しかしてはいけないらしいのでCoiL氏とざっくり分業の相談をする ← レギュレーション思ってたのと違ったっぽい(違ったっぽいので)

競技開始

開始して問題を読むとりあえずsubmissionするか！ということで縦にW回横にH回動くやつをする HとW逆だったらしいけどまあこのテストケースやったらうまくいってるしええやろ！ｗ

提出すると1072点、意外と点数のスケールが小さいことがわかる(10:05:41)

アルゴ脳なので一瞬でDPが思いつく実況で2行持つ全探索とか言われていた違います

dp : vector<vector> として、dp[i][j][k] := i行j列まで来たときkが作れる <=> 1 とすると、dp[i][j] = (dp[i - 1][j] | dp[i][j - 1]) >> n[i][j] となるので計算量がO(HW Σn)程度 H,W <= 30, -6000 <= Σn <= 6000なので余裕でDPによる全探索が可能(bitsetで定数倍 /64も乗るし) 実行時間 10^-1 s オーダーくらいじゃないですかね知らんけどなんで H,W <= 100じゃないんやろなあ〜(ヘラヘラ) いや実況でビジュアライザが点になるからって言われてたやんけ

これが大きいケースでうまくいくのはそれはそうで、例えば30x30の最短路は58 C 29 = 30067266499541040通りあって、値域が-6000から6000なのでさすがに-1,0,1のやつは存在することがとんでもなく期待される 10x10だと48620通りあって値域が-1000から1000なので盤面がランダムなら中央付近の期待値爆上がりなので(正規分布に近似されていく)そこそこ期待できる 5x5だと70通りを-500から500 まあそれなりに知らんけど

提出するとINF点あれ？？？→左右間違えて盤外に出ていた修正して提出すると71点勝ったなガハハ！ｗ(10:47:42)

CoiL氏が全探索が書けたらしいのでマージするしようと思ったらお互いグローバルに無限にものがあって困っちゃったのでnamespace CoiL{}とnamespace Naan{}で囲む別にイキってnamespaceをつけたわけではないんじゃ

マージしたコードを投げると3x3がやばいスコアになっているこれは乱数ガチャやろ〜と思って大量になげる

どうにもおかしい(最初の最短路全探索より悪いのしか出ない)ので全探索こわれてないかということになる二人で修正にとりかかる自分は一から書く時間とCoiL氏のコードを読み解く時間もなかったので手で全列挙をするおねえさんの問題を3x6まで全列挙した経験が生きる！！！！！実際3列の場合はフロンティア法の状態がたかだか5個なので一瞬で列挙が可能なので一瞬で列挙した

書いて投げる 57点でわいわい(11:11:32)

5x5も全列挙するか〜という気持ちになるけど8512通りは頭がこわれる上フロンティア法の状態が無限個あって禿げたもはやコード修正の時間はなさそう †偶然†持っていたまちカドまぞく(1-4巻,伊藤いづも,芳文社)をPCの前にお供えしていい乱数を引けるように祈祷して提出する乱数乞いに成功して36点(11:17:05) 残り1分切ったし優勝では？→優勝

競技終了

優勝して気が大きくなるインタビューに答える LIVEのアーカイブを見ると想定した1/100倍くらいしか声が伝わっていなくておっぱげた

CoiL氏の功績があんまり実況側に伝わっていなさそうで悲しかったバグは入出力高速化の位置が原因でnaanがコードをマージするときに埋め込んだっぽい申し訳なさすぎて申し訳のNASAofNASAになったそこ修正したら16点くらい出たこれマジ？反省した

駒場に+200点！実質グリフィンドール(ほんまか) いやーなんだかんだ言って実質アルゴみたいなアプローチができたので楽しかった次の駒場祭ではもっと貢献していきてえなあ俺もなあ

いろいろ終了後

帰り道新ABCに出たなんとか全完したやったぜ。アルゴ最高〜〜〜次回のTSG LIVE! ライブ競技プログラミングはアルゴとマラソンの2回開催ってマジ？マジじゃないです

はいなんだよね(はいなので)

TSG LIVE! 3 day 2 ライブ競技プログラミング write up

Day 1 - 開始直前

競技開始

競技終了

いろいろ終了後