きままにものづくり

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

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

コード

広告を非表示にする