問題

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

数列 a_n から 3 点を選択して、数列を連続する 4 つの部分列に分解する。各部分列の総和を P, Q, R, S とする。

| max(P, Q, R, S) - min(P, Q, R, S) | の最小値を求めよ。

制約

4 <= N <= 2 * 10⁵
1 <= a_i <= 10⁹

考え方

全探索＋二分探索の組み合わせ。解を求めるためには、a_n を 3 点を選んで区切る必要があるが、これは真ん中を固定するとうまくいく。まず真ん中で 2 つに分けた後、それぞれをさらに 2 に分けるが、これは各要素がなるべく均等になるようにすると良い。総和の数列は単調増加になっているため、二分探索でなるべく均等になるように分けることができる。

全探索パートは特に難しいことはない。数列 a_n の閉区間 [b, e] における要素をなるべく均等に分ける方法について考える。

数列 a_n の閉区間 [b, e] を P : sum[b, m], Q : sum(m, e] の 2 つに分けるとき、なるべく均等に分ける方法は次の 2 のパターンが存在する。

(i) P <= Q
(ii) P > Q

たとえば次のような数列を考える。

a_n = {1, 2, 4, 5, 7, 9}

i	1	2	3	4	5	6
$a_i$	1	2	4	5	7	9
$sum$	1	3	7	12	19	28

このとき
(i)P <= Q となるように分けると、[1, 4], (4, 6] となり P = 12, Q = 16 となる。
(ii)P > Q となるように分けると、[1, 5], (5, 6] となり P = 19, Q = 9 となる。
この場合は | P - Q | の差が小さくなるのは (i) の場合であるから、(i) で分割するのが最適である。

次にサンプル 2 を例に、全探索の後半部分の区間 [6, 10] を 2 つに均等に分ける方法を考える。

i	4	5	6	7	8	9	10
$a_i$	…	…	47	23	25	52	64
$sum$	…	204	251	274	299	351	415

まずこの区間 [6, 10] の総和 sum[6, 10] は 415 - 204 = 211 である。[6, m], (m, 10] となるように m を選択する。区間の総和に対して P がどこまで大きくできるかを考える。累積和の数列は単調増加であるから2 * P と sum[6, 10] を比較して、2 * P <= sum[6, 10] となる最大の index を二分探索で求めればよい。

       long[] a, sum;
        public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt();
            a = new long[n+1];
            sum = new long[n+1];
            for (int i = 1; i < n+1; i++) {
                a[i] = in.nextLong();
                sum[i] = sum[i-1] + a[i];
            }

            long min = LINF;

            for (int i = 2; i < n-1; i++) {
                P p1 = calc(1, i);
                P p2 = calc(i+1, n);

                List<Long> list = new ArrayList<>();
                list.add(p1.a);
                list.add(p1.b);
                list.add(p2.a);
                list.add(p2.b);

                Collections.sort(list);

                min = Math.min(min, list.get(3) - list.get(0));
            }

            out.println(min);

        }

        // 閉区間 [b, e] 上の sum の差を最小にする値を求める。
        P calc(int b, int e) {

            int l = b, r = e;
            long hs = sum[r] - sum[l-1];

            // P <= Q となる位置 l を探す
            while (r - l > 1) {
                int m = (r+l)/2;

                long ls = sum[m] - sum[b-1];

                if (ls * 2 <= hs) {
                    l = m;
                } else {
                    r = m;
                }
            }

            // P <= Q の場合
            P ret1 = new P(sum[l] - sum[b-1], sum[e] - sum[l]);

            // P > Q の場合
            P ret2 = new P(sum[l+1] - sum[b-1], sum[e] - sum[l+1]);

            if (ret1.a - ret1.b > ret2.b - ret2.a) {
                return ret1;
            } else {
                return ret2;
            }

        }

      class P {
            long a, b;

            public P(long a, long b) {
                super();
                this.a = a;
                this.b = b;
            }

        }

閉区間 [b, e] 上の sum の差を最小にする値を求める実装が大変であった。

ポイント

3 点選択は真ん中固定
(非負数で構成される)数列の累積和は単調増加

数学/競プロメモ

ABC102-D：Equal Cut(600)

問題

考え方

ポイント