World Finals

A

ひとまずsmallは全部試すだけだったのでとりあえず出すかと思ったら、なぜかEclipse上で実行できない…
どうやらJREのデフォルト設定がおかしいっぽく、設定し直したりして無駄に時間を食ってしまったorz
プラクティス中にちゃんと試しておくべきだったorz
条件を満たす領域は、２変数で考えるとただの三角形で、片方固定すればただの線分なので、下から順に見ていけばO(n^2)でlargeも解ける。

B

smallは塗りつぶすだけ
largeは片方全部回して…とかではできなさそうでむずい

C

smallは2^2n試すだけ
largeは和に注目すると、実は一意に定まるんだとか…
よく分らないｗ

D

smallは二つの森からの距離のうち近い方の和に森につなげるためのコストを加えるだけ
largeは森をつなげる部分を最小全域木にすればよい？？
よく分らないｗ

E

smallは2^2nのDPではビミョーに間に合わず、２回もミスってしまったorz
マルチスレッドテンプレートを作ってくるべきだったと後悔しながら考えてたら、連続する３つの?を全て#にして解がよくなることはあり得ないことに気づいたので、その部分を枝狩りしたら間に合った
largeはどう見ても最小カットだろーと思いながらも、かなりの時間考えていたが、結局解けなかった。
カット後に、始点に接続→使う、終点に接続→使わない、となるようにグラフを作ると、負の辺ができてしまって、負の辺の最小カットってどうやるんだーとなって詰まってしまった。
終了後に考えてたら、チェス盤の白黒で分割して、片方逆向きにすればいいだけだったorz
結局負の辺がある時の最小カットを求めるのは無理なんだろうか…

結果はA~EのsmallとAのlargeを通して36点の40位orz
来年もあるなら次回こそはもっといい順位をとってやる〜