らての精進日記

修行をします

aoj2382:King Slime

解法

垂直または水平に隣り合うやつらに辺を張ってグラフを作ってみる。適当に全域森をとると、それぞれの木は、(木のサイズ)-1回の操作で1つの頂点にできる。これをすべての木についてやると、どの2つのスライムも垂直または水平に隣り合わないような感じになる。あとは、壁に寄せて一直線上に並ばせて、最後に全部くっつければいい。

恐らくこれが最適な操作だと思うが、証明とかはできてない(こういうアルゴリズムの最適性の証明みたいなやつ、ムズすぎて死ぬ)

ただ、少しだけ得をできるケースがあって、「壁に寄せて一直線上に並ばせる」という操作のときに、最初から壁際にいる奴らについては、操作を1回分なくせる。よって、どの壁に寄せるか(4通り)をすべて試して、それぞれに対して、最小のコストをUFとか使って求める。


コード