AtCoder Grand Contest 027 B - Garbage Collector

https://beta.atcoder.jp/contests/agc027/tasks/agc027_b

まずゴミを捨てる回数mを決めた時の最適な捨て方を考えます。

考えやすいようにm台のロボットを並列に動かして、行きのエネルギー(位置0からそれぞれのロボットが拾う一番遠いゴミまでの移動)を無視して帰りのエネルギーだけ考える。

ある地点を通るときのゴミの個数の分布が{0,2}の場合、ゴミを別のロボットに渡して{1,1}とすることでエネルギーの総和を減らすことができる。一般にゴミの個数をk-1個からk個に増やした時の増加エネルギー(k+1)^2-k^2=2k+1 は狭義単調増加であるため、ゴミの個数が2個以上離れているロボットがいればゴミを受け渡すことである地点を通るために必要なエネルギーの総和を減らすことができ、均等にゴミを持たせるのが良いとわかる。ゴミを均等に持たせた状態は位置0に帰るまで維持できるので明らかに最適である。

行きのエネルギーを1とした場合、ゴミを均等に持つために行きの移動量が増えたとしても1しか増えないのでトータルで損にはならず、それぞれの地点でゴミを均等に持てばいいという結論に影響はない。

 

最適なゴミを捨てる回数mを求めるのは勘で三分探索をやった(未証明)

ちゃんとmを全探索することを考えるとロボットがある個数のゴミを持って移動する範囲は区間になっているので累積和を計算しておくと計算量が調和級数O(N \log N)になる