Garbage Collector [AtCoder Grand Contest 027 B]

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;
}