かなり悩んだ

問題概要

長さ $N$ の整数列 $A$ を 3 箇所で切って、4 つの連続する数列に切り分ける。このとき、4 つの区間の値の和を $P, Q, R, S$ とするとき、 $\max(P, Q, R, S) - \min(P, Q, R, S)$ の最小値を求めよ。

制約

$4 \le N \le 2×10^{5}$

考えたこと

こういうの、

連続する区間が 4 個だけであることを活かす解法
連続する区間が k 個でもいい解法

のどちらになるケースもあって判断難しい。今回は 4 個であることを活かすタイプの問題だが、後者のタイプの問題として ABC 104 D - We Love ABC とかがあった。

さて、今回の問題では、数列を 4 つの区間に分割するということで、すなわち切れ目を 3 箇所に入れる問題である。3 つの場所について考察するような問題では

真ん中を固定する

というのが一つの定石である。今回もそれに沿ってみる。まずは真ん中の区切れ目を固定する。

さて、この手の最適化問題ではある種の考察の仕方の典型がある気がする。

最適性条件 (どういうときに最適になるかの条件) を見出して、最適性条件から解を変形させると解が悪化することを示す

というのが 1 つの考察の流れな気がする。今回で言えば、ひとまず真ん中を固定したときに、左半分を X、右半分を Y とすると、X = P+Q、Y = R+S となるわけだが、

P と Q の差が最小 (P と Q が均等)
R と S の差が最小 (R と S が均等)

になるのが良さそう。少し考えると、X と Y が固定であっても上記のケースが全体でも最適になることがわかる。例えば

X < Y だったら、min(P, Q) があまり小さくなってほしくないし、max(R, S) があまり大きくなってほしくない
X > Y だったら、max(P, Q) があまり大きくなってほしくないし、min(R, S) があまり小さくなってほしくない

こういう風に考えてみると、結局「P と Q がなるべく均等」「R と S がなるべく均等」になるのがよいことがわかる。より正確に言うと、P + Q = X を固定したときに、

P < Q となる最右の切れ目
P >= Q となる最左の切れ目

の両方を試して、より P と Q の差が小さい方を採用すればよい。

あとは、

真ん中の切れ目を i 番目で固定したときの、「P と Q の最適な分け方」「R と S の最適な分け方」

を求めてあげればよい。これはしゃくとり法でできる。

真ん中の切れ目 i を固定したときに、P と Q の最適な切れ目 f(i) も、R と S の最適な切れ目 f(i) も、 i について単調増加である

という風になっているので、しゃくとり法がはまる。でも今回は

累積和 + 二分探索

でやってみることにする。

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<long long> A;
vector<long long> sum;

int main() {
    cin >> N; 
    A.resize(N); sum.resize(N+1); sum[0] = 0;
    for (int i = 0; i < N; ++i) cin >> A[i], sum[i+1] = sum[i] + A[i];

    long long res = 1LL<<60;
    for (int i = 0; i <= N; ++i) {
        // P < Q となる最大の切れ目を求める: 二分探索を終えた時の left_low
        int low = 0, high = i;
        while (high - low > 1) {
            int mid = (low + high) / 2;
            if (sum[mid] >= sum[i] - sum[mid]) high = mid;
            else low = mid;
        }
        long long P = sum[low], Q = sum[i] - sum[low]; // 候補1
        long long P2 = sum[high], Q2 = sum[i] - sum[high]; // 候補2
        long long left_min = min(P, Q), left_max = max(P, Q);
        if (abs(P2-Q2) < abs(P-Q)) left_min = min(P2, Q2), left_max = max(P2, Q2);

        // R < S となる最大の切れ目を求める
        low = i, high = N;
        while (high - low > 1) {
            int mid = (low + high) / 2;
            if (sum[mid] - sum[i] >= sum[N] - sum[mid]) high = mid;
            else low = mid;
        }
        long long R = sum[low] - sum[i], S = sum[N] - sum[low]; // 候補1
        long long R2 = sum[high] - sum[i], S2 = sum[N] - sum[high]; // 候補2
        long long right_min = min(R, S), right_max = max(R, S);
        if (abs(R2-S2) < abs(R-S)) right_min = min(R2, S2), right_max = max(R2, S2);

        // 真ん中の切れ目が i であるときの暫定解
        long long tmp = max(left_max, right_max) - min(left_min, right_min);
        res = min(res, tmp);
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 102 D - Equal Cut (ARC 100 D) (1D, 青色, 600 点)

問題概要

制約

考えたこと