AGC027 B - Garbage Collector - ツバサの備忘録

解法

ゴミを回収しに行く回数(=ゴミを捨てる回数)を $k$ 回と決め打ちし、そのときの最小値を求めます。
そして、最後に $k$ について全探索して答えを求めることを考えます。
$k$ 回ゴミを回収しに行くとき、ゴミを拾う回数は $n$ 回、捨てる回数は $k$ 回なので、 $(n+k)×x$ 足す必要がありますが、これは値が $k$ にしか依存しない(他が定数)ので、これ以降は考えないことにして、最後に足します。
今、1回の収集で $p$ 個のゴミを拾うことについて考えます。
少し実験するとわかるのですが、ゴミを回収する際は、できるだけ遠い場所に行き、その帰り道にゴミを回収していくのが最も効率がいいです(これは、手持ちのゴミが多いと消費エネルギーが多くなるためです)。
左から $i$ 番目のゴミを $j$ 番目( $1$ ~ $p$ )に回収するとき、増加するエネルギーについて考えると、

$j=1$ のとき
$x_i$ に向かうのにエネルギーを $x_i$ 、そこからゴミを回収して原点に帰るのにエネルギーを $4×x_i$ 消費します。合計で
$5×x_i$
消費します。
$j \neq 1$ のとき
$x_i$ から帰るときの消費エネルギー $(1+y)^{2}×x_i$ は、 $j-1$ 以下までの計算である程度計算されています。
ので、足りない分を追加してあげる必要があります。
$(1+y)^{2}$ は、 $y$ が1増えると $2×y+1$ だけ増加します。今、 $j-1$ 以下で $(1+j-1)^{2}$ まで計算されているので、 $(1+j)^{2}$ にするために $2×j+1$ だけ増加させます。ということで、増加エネルギーは
$(2×j+1)×x_i$
となります。

ということで、上記の式を用いて計算することで、 $p$ 個のゴミを1度に回収する場合の消費エネルギーを求めることができるようになりました。
さて、 $p$ 個のゴミの決め方、および $k$ 回回収するなかでのゴミの個数の振り分け方を考えます。
先ほどの式を見るとわかるように、 $p$ の個数が多いほど、消費エネルギーを計算する回数が増えるので、それだけ消費エネルギーが増加してしまいます。なので、1回あたりの回収する個数はできるだけ少なくしたいです。ということで、平均的にする必要があります。
また、距離が遠いほど、消費エネルギーはもちろん多くなります。なので、ここにかかる係数(具体的には $5$ 、もしくは $(2×j+1)$ です)を小さくしたいです。なので、遠いゴミは、同時に拾うのをできるだけ避けたいです。
ということで、

できるだけ1回あたりに拾う個数を平均的に
遠いゴミを同時に回収することを避ける

とすると、次のように回収することになります。
$n, n-1, ... n-k+1$ 番目のゴミは、 $k$ 回回収するなかでそれぞれ1番目(手元にゴミがない状態のとき)に回収
$n-k, n-k-1, ... n-2k+1$ 番目のゴミは、それぞれ2番目(手元にゴミが1個の状態のとき)に回収
と続いていきます。端数が発生した場合、とくに気にせず足していきます(その端数分で1つのくくりにします)。
つまり、ゴミを遠い方から順番に $k$ 個ずつ選び、そのまとまりごとに1番目に回収、2番目に回収、としていくと、 $k$ を固定したときの最適解となります。
これをもとにして、上で述べたような $5×x_i$ および $(2×j+1)×x_i$ の式に当てはめていくのですが、 $x_i$ の部分を、 $j$ 番目に回収するゴミをまとめて一気に処理する方法があります。累積和です。
$sum[i]=$ $i$ 番目までの $x_i$ の総和
とすると、
たとえば1番目に回収、すなわち $5×x_i$ の式に当てはめるものは、 $n-k+1$ ～ $n$ についての $x_i$ なので、
$sum[n] - sum[n-k]$
となります。これを $x_i$ の部分に代入してあげれば、まとめて処理できます。
あとは、これを計算していった結果と、 $(n+k)×x$ の和を求めれば、 $k$ を決め打ちしたときの最適解になります。
$5×(sum[n] - sum[n-k])+(2×j+1)(sum[n-(j-1)k]- sum[n-jk])$
$+(n+k)×x$
となります( $j$ は2以上です)。
あとは、 $k$ について全探索して、最小値を求めれば、答えが求まります。