問題概要

ゴミ (ゴミの数$ N \leq 2 \times 10^5 $) を拾う・運ぶ・捨てるエネルギーが以下のように定められるとき，全てのゴミを捨てるまでの消費エネルギーを最小化せよ．

i番目のゴミはそれぞれ$ x_i (\leq 10^9)$の位置にある．
k個のゴミを運んでいるときは距離1につき$ (k+1)^2$のエネルギーを消費する．
ゴミ箱は座標0にあり，全てのゴミはここに捨てなければならない．ゴミをゴミ箱以外のところに置いておくことはできない．
ゴミを拾うときとゴミ箱に捨てるとき，それぞれ$ X ( \leq 10^9 )$のエネルギーを消費する．
ゴミ収集ロボットは座標0からスタートする．

解法概要

この問題は，座標0のところにゴミを捨てる回数をkと固定すれば「k台のロボットが一斉にスタートし，ゴミをいくつか拾って座標0のところに戻ってきてゴミを捨てる．ロボットのエネルギー消費量の和を最小化するにはどうしたら良いか」という問題に言い換えられる．この言い換えをすると，

どんなゴミの集め方をしても1つのゴミを拾うのにXのエネルギーを消費するので，これは最小化の時には無視していい． (最後にNXを足せば良い)
座標0のところにゴミを捨てる回数をkと固定すればゴミを捨てるときのエネルギー消費kXも不変．

なので，最小化の時にはk台のロボットに対するN個のゴミの割り振りだけを気にすれば良いということになる．

また，移動時に持ち運ぶゴミの数はできるだけ抑えたいので，移動距離が同じなら遠くのゴミから順に拾っていったほうが得である．以降では，ゴミの座標はゴミ箱から遠い順 (つまり入力と逆順) に並んでいると仮定する．

そのロボットが担当するゴミの中ではゴミ箱からi番目に遠い，座標$ x_i $にあるゴミを追加で拾うとしたときのエネルギー増加は

$ E(i, x_i) = 5x_i\ (i = 1) $

$ E(i, x_i) = (i+1)^2 - i^2 = (2i+1)x_i\ (i \neq 1) $

である．あるロボットが4〜5個くらいのゴミを拾うときのエネルギー消費の式を実際に計算してみるとわかりやすい．例えば，あるロボットが担当するゴミが4個だったら

$ x_1 + 4 ( x_1 - x_2 ) + 9 ( x_2 - x_3 ) + 16 ( x_3 - x_4 ) = 5x_1 + 5x_2 + 7x_3 + 9x_4 $といった具合である．

このエネルギー増加の式から，k台のロボットを使うときはあるロボットに担当のゴミを集中させるより，各ロボットにバランスよくゴミを割り振ったほうがエネルギー消費が抑えられることがわかる．解説ではこれを「右からi番めのゴミは$ \lceil \frac{i}{k} \rceil $番めに拾えばよい」と表現している．

$ \lceil \frac{i}{k} \rceil $が同じゴミについては，あらかじめ$ x_i $の累積和を取っておけば計算量が抑えられる．

このときの計算量は$ O(\sum_{i=1}^{N} \frac{1}{i}) = O(\log N) $である (Nを十分大きいとすると，$ \sum_{i=1}^{N} \frac{1}{i} \approx \int_1^N \frac{1}{x} dx = \log N $ のため．1, 1/2, 1/3, ...などのような「逆数が等差数列になるような数列」を調和数列というらしい．私の出身高専では多分習わなかったので初めて知った．)

実装時にはオーバーフローに注意．何も考えずに64bit整数を使うと2つのケースでやられる．私は多倍長整数 (参考: 多倍長整数 - boostjp) で対処したが，オーバーフローしてエネルギー消費が負になったら絶対値の大きな正の値を代入して対策する方法もあるようだ (参考: AGC027-B 「Garbage Collector」 (700) - Mister雑記)．

ソースコード

    #include <iostream>
    #include <boost/multiprecision/cpp_int.hpp>
     
    using namespace std;
     
    typedef long long ll;
    typedef boost::multiprecision::uint128_t uint128_t;
     
    int main() {
        int n; ll x;
        cin >> n >> x;
        ll a[n];
        for(int i=0;i<n;++i) cin >> a[n-1-i];
        for(int i=1;i<n;++i) a[i] += a[i-1];
     
        uint128_t ans = (uint128_t(1) << 90);
        for(int k=1;k<=n;++k) {
            uint128_t tmp_ans = x * ll(k+n);
            tmp_ans += 5LL * a[k-1];
            for(int i=1;i<(n+k-1)/k;++i) {
                tmp_ans += ll(2*i+3) * (a[min(n-1,k*(i+1)-1)] - a[min(n-1, k*i-1)]);
            }
            ans = min(tmp_ans, ans);
        }
        cout << ans << endl;
    }

所感

自力でやろうとしたときは何をすればいいか皆目見当がつかなかったけど，解説見たら手を動かしながらじっくり詰めていけば不可能ではないということがわかり，好きになった．好きなので久々に解説を書いた．

NoiminのNoise

AtCoder Grand Contest 027 B - Garbage Collector

問題概要

解法概要

ソースコード

所感