KUPC 2012 - #ichyomemo

京都大学プログラミングコンテストにオンサイト参加した．
5時間の長丁場だけど，時間をフルに使えた気がするし，問題も楽しかった．ジャッジさんお疲れ様でした．
結果は703点で30位．欲を言えばあとK問題の60点は取りたかった…．

x, 2*x, ... を E + Tを超えるまで計算する方法でやった．O(NT)?

１分ほどながめても全然わからんからとばした．開始三時間ぐらいで，左端に置く，右端に置く，パスを，頭から優先的に選ぶシミュレーションを書いたらなぜか通った．解説聞いてもよくわからんかった．

各うさぎについて，仲の悪いうさぎがいるかどうか計算するだけ．50*50の配列作ればいいところを，わざわざsetでやってしまった．反省．

最初，最小費用流で解ける問題だと勘違いしていて，ここでだいぶ時間を食ってしまった．最終的には貪欲的に解けると気づけた．
「1を含む範囲のなかで終点が一番大きいものを選ぶ→前回選んだ範囲の次の部屋を含む範囲のなかで終点が一番大きいものを選ぶ→」を繰り返せば良い．

最初は勝ちの数が多いほど手が出やすくなるようなランダム選択をした．1つのケースだけうまく行かなかったので，前半500と後半500に分けて，前半で得られたポイントの数を数えて，後半はポイントを得やすい手を選ぶようにした．

1日ごとの処理を頑張って速くする問題かなーと思った．サービスを復旧時間順にソートするとか，復旧した時点で，それ以降の復旧度の増加値を計算するとかをやったら，5秒制限を4.3秒で通った．やってることはO(Day * x)なので，最悪ケースだと計算量が10^10になってダメな解法(?)

xでソートして枝刈りをする嘘解法っぽいのを出したら，一個だけTLEになった．がんばって定数倍高速化してみたけどぜんぜん意味がなかったし，45度回転させたら通ったので最初からそれをやるべきだった．

読んでない

点を二つ選んで角度を求めると直線が二つ作れるので，その交点を選ぶようにした．ローカルのリアクティブプログラムだとE=0のときは常にACがでるのに，サーバー側だと1つのケースしかACが出なくて謎だった．いろいろごにょごにょやってたら通ったので多分誤差の関係．

読んでない

bfsでint memo[N][2^M] の配列を埋めるような解法で部分点取れるかと思ったが１個だけTLEが出てダメだった．O(N*N*2^M)なのでさすがにだめか…．