きままにものづくり

日々の気付いたことなんかを書いてます。

SRM642Div1Medium

問題

H個の木がある。各木のはじめの高さは $h_i$ で与えられ、 $add_i$ の高さだけ毎日成長する。木を切るためのデバイスがD個与えられる。これは、高さが $D_j$ 以上の木を高さ $D_j$ に切ることができる。その日の最後にデバイスを使用することができる。各デバイスは1日に一度しか使えず、各木は1日に一度しか切れない。以上の操作を行ったときのT日目の木の高さの総和の最小値を求めよ。

解法

最小費用流を用いる。以下のようにエッジを張る。ノードには木、デバイス、日とsource、sink、noneがある。noneはデバイスを全く使用しないための頂点である。

sourceと各木を、容量1、コスト0で結ぶ
各木とnoneを、容量1、コスト $h_i + add_i*T$ で結ぶ。
noneとsinkを、容量H、コスト0で結ぶ。
各木と各日を、容量1、コスト(T-k)で結ぶ。kはデバイスを使用する

日を示す。

各日と各デバイスを、容量1、コスト $D_j$ で結ぶ。
各デバイスとsinkを容量T、コスト0で結ぶ。

この処理では、木の高さが $D_j$ 以下でもデバイスを使用してしまっている。しかし、求めたいの木の総和の最小値であるため、この時が最小値となることはないため、正しく答えを計算できる。

計算量

$O(H * (H + D + T) * min(HT, TD) ) = O(N^4)$
N: max(H, D, T)
H: 木の数
D: デバイスの数
T: time

コード