https://beta.atcoder.jp/contests/agc027/tasks/agc027_b
数直線上のいくつかの座標にゴミが置いてある。0の位置にはゴミ箱があり、数直線状を移動しながらすべてのゴミをゴミ箱に入れる。ゴミを拾うときと捨てるときに$X$のエネルギーを使い、$k$このゴミを持っている間は1移動するたびに$(k+1)^2$のエネルギーを使う。目的を達成するのに必要な最小のエネルギーを求めよ。
ゴミ箱から出発していくつかのゴミを拾い、またゴミ箱に帰ってくるまでを1往復と呼ぶ。ある往復で、座標 $a, b, c, d, e$ (近い順)にあるゴミを拾ったとしたとき、持っているゴミの数が移動コストに影響することを考えるとゴミ箱から遠いものから拾うのが明らかに最適である。移動にかかるコストだけに注目すれば、行き(ゴミを持っていないので単位距離あたり1)と帰りを足し合わせて $$5(e-d)+10(d-c)+17(c-b)+26(b-a)+37a$$ となる。これを展開すれば $$5e+5d+7c+9b+11a$$ のようになり、拾ったゴミの座標から移動のコストを求められる(この係数はゴミを拾った数に関係なく、1つめのゴミだけ例外的に$5$で、nつめのゴミについては$1+2n$となっている)。
往復の回数をK回に固定したときを考える。このとき、ゴミを拾ったり捨てたりするコストは$(K+N)X$で固定になるため考えなくてよい。K回往復するので、前述の係数をそれぞれK個ずつ使うことができて、遠いゴミに小さい係数を割り当てるのが最適であるから、もっとも遠いKこのゴミに係数5を、その次に遠いKこのゴミに係数5を、その次には係数7を、というように割り当てていく。これは累積和を使えばうまくできる。
最後に、ゴミ箱に行く回数を1回からN回まで全探索すれば最小のエネルギーがわかる。計算量は、$N/i$の和がlogで抑えられることを利用して$O(N\log N)$。
コンテスト中はこの問題に130分以上かけたはずだが考察を詰め切れなかった。遠い順に拾うのが最適であることや、ゴミを1つだけ拾ったときと2つ拾ったときで最終的な移動コストが同じであることなどには気づいていたが……