TCO09 Round2

250

なんかバグって時間かかってもうダメぽorz
205.75

600

600と900どっちから開こうか悩んだが900難しいといやなので600からやることに。
極大三角形の個数を求めればよくて、極大三角形は凸包上の点からなる。
凸包上の点の個数はO(n)なのでO(n^3)で全部調べても間に合う…
つもりだったんだけど、なんかTLEしたので定数倍高速化して再提出orz
269.26

900

とりあえずフローを流してみて、(i,j)の辺を使っている場合に残容量グラフでi->jのパスが別に存在すれば、そっちに切り替えられる。
よって、辺を辞書順に見て行って、使っている辺をそれ以降のやつで切り替えれるかO(n^2)で調べられてO(n^4)だーと思って組んでみたが、なんかバグったorz
時間がなくなってきたので、仕方なく、毎回１から流してもDinicなら間に合うに違いないと信じてやり直したがこっちまでバグったorz
プラクティスで試したところ毎回DinicはTLEで、やろうとしてた奴はなんかWAだったのでまぁしょうがない
(追記)やっぱり方針はあっててバグってただけだったorz

Challenge

撃墜ミスって600まで落ちた場合通過できなくなるので安全策をとって撃墜せず

合計475.01の80位
2830 → 2824
下がったけど、まぁ通過できたのでよしとしよう