Equal Cut [AtCoder Regular Contest 100 D]

https://beta.atcoder.jp/contests/arc100/tasks/arc100_b

考察過程

1. 区切り目が3つある
2. なにかの全探索を考えるが、2番目の区切り目が良さそう（バランス）
3. 最大値と最小値の差を小さくするには、なるべく均等に分けるのが良い
4. 1番目と3番目の区切りは貪欲に決めていいのでは？（予想）
5. AC

解法

https://beta.atcoder.jp/contests/arc100/submissions/2798606

全探索と貪欲法で解く。
3つの区切り目を用意して、PQRSに分ける。
区切り目をabcとすると、
Pは[0,a)
Qは[a,b)
Rは[b,c)
Sは[c,N)
として考えられる。
　
bを全探索しよう。
すると、aはPとQの差を最小化するようなa, cはRとSの差を最小化するようなcと貪欲に決定できる。
このaは二分探索でPとQの大小の境界を見つけて、P≦Qとなる最大のa, P＞Qとなる最小のaについて最小化される方を採用すればいい。
cも同様に決定できる。
　
これでO(NlogN)で大丈夫。
しゃくとり法を使えばa,cの特定はO(1)で行える。

int N, A[201010];
//---------------------------------------------------------------------------------------------------
ll B[201010];
ll get(int L, int R) { // [L,R)
    if (L == R) return 0;
    ll res = B[R - 1];
    if (L) res -= B[L - 1];
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
 
    B[0] = A[0];
    rep(i, 1, N) B[i] = B[i - 1] + A[i];
 
    ll ans = infl;
    // [0,a) [a,b) [b,c) [c,N)
    rep(b, 2, N - 1) {
        int a, c;
        ll P, Q, R, S;
 
        {
            int ok = 0, ng = b;
            while (ok + 1 != ng) {
                int md = (ng + ok) / 2;
                if (get(0, md) < get(md, b)) ok = md;
                else ng = md;
            }
            vector<int> v;
            if (ok) v.push_back(ok);
            if (ok + 1 != b) v.push_back(ok + 1);
            if (v.size() == 1) a = v[0];
            else if (1 < v.size()) {
                int a0 = v[0], a1 = v[1];
                if (abs(get(0, a0) - get(a0, b)) < abs(get(0, a1) - get(a1, b))) a = a0;
                else a = a1;
            } else assert(0);
        }
        
        {
            int ok = b, ng = N;
            while (ok + 1 != ng) {
                int md = (ng + ok) / 2;
                if (get(b, md) < get(md, N)) ok = md;
                else ng = md;
            }
            vector<int> v;
            if (ok) v.push_back(ok);
            if (ok + 1 != N) v.push_back(ok + 1);
            if (v.size() == 1) c = v[0];
            else if (1 < v.size()) {
                int c0 = v[0], c1 = v[1];
                if (abs(get(b, c0) - get(c0, N)) < abs(get(b, c1) - get(c1, N))) c = c0;
                else c = c1;
            }
            else assert(0);
        }
 
        P = get(0, a);
        Q = get(a, b);
        R = get(b, c);
        S = get(c, N);
 
        ll mi = min(min(P, Q), min(R, S));
        ll ma = max(max(P, Q), max(R, S));
 
        chmin(ans, ma - mi);
    }
 
    cout << ans << endl;
}