ICPC2014国内予選 - わふぅ。

落ちました。来年は全完できるようにがんばります。

シミュレーションするだけ。

行ごとに消去されるブロックをチェックして消したあと、列ごとに下からブロックを積みなおす、という作業を繰り返すだけ。

木DPっぽさがあるが、すこし考えると直径を求めておしまい。

元のグラフGからリーフを切り取ったグラフG'を考えれば、答えは「Gの全長 + G'の全長 × 2 - G'の直径」で、あとは O(n) なコードを書くだけ。ちなみにこれは、グラフG'上での直径を実現する端点S,Tを考えれば、Sから作業を始めてTで作業を終えるときの最小コストに等しくなる。