ferinの競プロ帳

競プロについてのメモ

チーム練習 12/6

チーム練習で 2017-2018 ACM-ICPC, Asia Daejeon Regional Contest をやった.7完1035で本番23位相当だった.記憶にない場所があるのでだいぶ嘘が混じってるかも

(開始) divくんと手分けして読みつつ.おるふぇがテンプレを書く.Dが簡単らしいのでおるふぇが書きはじめる.
(11分) Dが通る.Cが通ってるので概要を聞くと,DAGなのでおわり.おるふぇが書き始める.Lについて,先週やった去年のソウルのJっぽく頂点組 (a,b,c) にたどり着くのに必要な最小のコストとか持てばよさそうだな~とdivくんと相談している.
(21分) Cが通る.Lを書き始める.この間に二人がE,Fを考えてた.Eがフローっぽいらしく,dinicの計算量は O(V^2E) だよ,貼るなら俺書くよ~とか言ってた.
(46分) Lを投げたらTLEでかなしい.O(M^3\log N), M \leq 200, N \leq 50 って落ちるのか….Fが解けるらしいので実装を交代する.Eはコストが小さい辺から追加していってループができるならフローを流せばいいらしいけどフロー毎回流せるかがかなり微妙(は?)みたいな感じになった.HIが通ってるので読む.
(1時間31分) Fが通る.Lを定数倍高速化して投げたけど通らないのでおしまいです.このあたりで解法が出てる問題がなくなる.HILKあたりをやる.Hは1ずつずらす差分を高速に計算とかFFTとか出るけど詰めきれない.Lは高々 n 回しか移動しなさそうだし独立に3回bfsすればいいんじゃね?とおるふぇが思いついたので書き始めるが,冷静になると O(n^3) 回移動するパターンに気づく.dijkstraだめだったしこれも通らないなあって言ってやめる(は?).おるふぇがKの解法を生やしたので実装始める.Iを考えると周期だしZ-algorithmか~とか適当に言ってたら文字列逆にしてZ-algorithmやればいいことが判明する.早そうなので実装を交代して書き始める.
(2時間52分) Iが通る.Kを書いてもらう.Hを考えてると,R,S,Pを独立に考えればFFTできることにdivくんが気づく.
(3時間21分) Kが通る.Hを書き始める.二人がBとかGの解法を生やしてる.入力が64通りしかないからBは埋め込めるらしい.
(3時間48分) Hが落ちる.Bを書いてもらう.境界を冷静に考えるとおかしいことに気づくので代わってもらってHを書く.
(4時間3分) Hが通る.おるふぇがGを書く.
(4時間16分) Gが通る.おるふぇがBを書く.divくんとEを考えているが何も浮かばない.残り25分くらいでEがわからずBがバグってたのでBのデバッグを手伝うけど,残念ながら通らない.
(終了後) Lの解説を読むと見覚えのあることが書いてある.おるふぇが生やした解法だとdijkstraじゃなくてDPでいけるのでlogが落ちて通せる.Eの解説を読むと普通にフローを流していて?を浮かべるが,冷静に考えると最大流量 n だし重み1しかないし余裕で高速にフローが求まることに気づく(は?).

反省

  • E のフローが間に合うのに気づかないの何???
  • L の解法捨てたの厳しい
  • B の実装をちゃんと詰め切りたかった
  • HとIの解法生やすのがかなり遅い,これは瞬殺したい…

10完はしたいセットだったなあ.それにしても9完以上が15チーム,10完以上が11チームいるの韓国つよすぎないか

解説

2017-2018 ACM-ICPC, Asia Daejeon Regional Contest B - Connect3 - ferinの競プロ帳
2017-2018 ACM-ICPC, Asia Daejeon Regional Contest E - How Many to Be Happy? - ferinの競プロ帳
2017-2018 ACM-ICPC, Asia Daejeon Regional Contest L - Vacation Plans - ferinの競プロ帳

韓国語だけどgoogle翻訳でがんばると読める koosaga.com