ICPCdomestic2015 参加記

sleep 18000(@wafrelka @wo_M @sigma425)の3人で出ていました.
問題
順位表

東大内3位,全体4位で通過しました.やったぜ.

開始前
スクフェスをしたり


かわいい画像を送ったり
椅子を壊したり
しているうちにコンテストが始まる.
16:30 開始(0).とりあえずwafに印刷してもらう.その間0.cppみたいな汎用を作りコピーする.その後にAを書こうとしたが何も頭が働かなくて,後ろからwoに言われるままに実装した.なんか自分が書いてたとこ3,4箇所くらい間違えた気がする.(後ろからすぐそうじゃないみたいなのが飛んできたから大丈夫だったけど完全に無駄なことをした(woにやってもらうべきだった)) AC(1完7分)
印刷も終わってたしwafにBをやってもらう.その間に僕がC(演算子が出てきたのでやって,とか言われた),woがDをやる.Cは全然構文解析ではなかった.方針はすぐ経つけどちゃんと実装できるかなあとか思ってつめてるうちにBが通る(2完24分).wafはE,Fを読み始める.
Cを書き始める.stringのままやろうと思ってたけどさすがにやめたほうがいい気がしてきたので方針を変える.コンパイル通ったけどバグって泥沼化していたのでとりあえず印刷してwoにDをはじめてもらう.(42分)
ちょくちょく代わってもらってCをなおす.やっとサンプル通ったので提出,AC(3完55分)
woにDの続きをやってもらう.なんか気づいたら爆速で書き終わっていて一瞬でACしていた・・・プロ(4完67分)
Cまで泥沼感あったけどまあまあの順位になってた気がする.
ここではじめてPCが開いて,Gをwoにやってもらうのは確定だけどその前にEFを皆で考えることにしたけどEが読めず,なんか軽く説明されてもわからなかったので諦めてFを考えたら怪しい解法が生えたので説明するとwoに大丈夫じゃねとか言われたので実装する.結構ミスるポイントあった気がするけど気づけてうまく実装できたのでこれは割と満足.通った時は激アツだった(5完106分)
たしかここで東大3位,全体4位だったはず

その間につめてもらってたGをやってもらう.その間にE,Hを考えるけど解けない(Hは座標圧縮して確かめるだけだと思うけど多分実装時間足りないし列挙が下手くそで死にそうなのでこわい とかいって避けていた.)
1時間あるし大丈夫だろ～とか言ってたらサンプル1で2角形ができてしまい死.でもランキング全く変動しなかったのでこわいけど通過できた.


なんかAもCも危なくて戦犯になりそうだったがFが解けてある程度早く実装できたのでよかった.

F:
なんかマトロイドが2つあって・・・みたいな一般的なものが背景にあるらしくそっから貪欲が生えるらしいけどそんなのは知らない.
Bの辺それぞれに+xのcostをつけたときの最小全域木を考える.xがinfのとき,できるだけBの辺を使わないようなものが,-infのとき,できるだけ使うようなものが出来る.じゃあうまくxを変動させればちょうどN-1-k本使うやつも
でてくるんじゃね,ということで,"+xでBを何本使うか"をMSTで求める,N-1-k本以上使ってたらxの範囲を上げる,そうでなければ下げる,みたいなにぶたんをして,そもそもMSTが作れない場合やinfの時から-infの時の間にN-1-kが入ってない場合は解なし,とすると通った(最終的に出てきた全域木から(N-1-K)*xを引けばよい(これが答えになるのは,Bをある本数使うと決まってる中では今求めてた奴が一番小さいことが保証されてるから)

通過できた要因は,rngさんやjapljさんやskyさんやevimaさんなどがいなかったことと,Cxiv-Dxivのgoogle chromeが壊れたことです.