https://beta.atcoder.jp/contests/agc027/tasks/agc027_b
解法
https://beta.atcoder.jp/contests/agc027/submissions/3208323
何かを全探索するが、「ゴミを回収してゴミ箱へ捨てに行く」という操作の回数を全探索する。
k回ゴミ箱へ捨てに行く場合に必要なコストを考えてみよう。
Xエネルギー消費する回数は、ゴミの回収が合計N回、ゴミ捨ての回数がk回なので、(N+k)回になる。
移動に必要なエネルギーは例えば、1回のゴミ捨てでx[0],x[1],x[2], x[3], x[4], x[5]のゴミを回収する場合は、
13*x[0] + 11*x[1] + 9*x[2] + 7*x[3] + 5*x[4] + 5*x[5]となる。
係数が遠くの方から、5,5,7,9,11,13,...のようになっていく。
全てのゴミをどのようにkグループに分け、総コストを最小化することを考えると、
なるべく均等に分けることが最適である。
最適に分けると、遠くのゴミの方から、2k個が係数が5, k個が係数が7, k個が係数が9,...のように決定していく。
これでk回ゴミ箱へ捨てに行く場合の最適な必要コストが求まった。
後は、実装問題であるが、累積和を取っておき、係数ごとにコストを計算していく。
k=1では係数5が2個、7が1個、9が1個でO(N)
k=2では係数5が4個、7が2個、9が2個でO(N/2)
この調子で行くとO(N/k)の総和となるが、調和級数的(エラトステネスのふるい的)な計算量でO(NlogN)となる。
longlongでオーバーフローの危険性があるので、和を取るときに毎回上限に丸めよう。
int N, X, A[201010]; ll B[201010]; //--------------------------------------------------------------------------------------------------- ll get(int a, int b) { ll res = B[b]; if (a) res -= B[a - 1]; return res; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> X; rep(i, 0, N) cin >> A[i]; B[0] = A[0]; rep(i, 0, N) B[i] = B[i - 1] + A[i]; ll ans = infl; rep(k, 1, N + 1) { ll sm = 0; int R = N - 1; ll p = 5; while (0 <= R) { int L; if (R == N - 1) L = R - 2 * k + 1; else L = R - k + 1; L = max(L, 0); sm = min(infl, sm + get(L, R) * p); R = L - 1; p += 2; } sm = min(infl, sm + 1LL * X * (N + k)); chmin(ans, sm); } cout << ans << endl; }