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

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

JOI 本選 2014 C - バームクーヘン (AOJ 0600, 難易度 7)

JOI本選 JOI JOI難易度7 AtCoder AOJ しゃくとり法 数珠 二分探索 最大値の最小化 前処理 テク:循環するものを二週させる 非自明な線形時間 解空間:O(N^2)通りの選択肢 区間 「次の要素」へのポインタを求める

以前にしゃくとり法の記事で特集した問題のひとつだった！

問題概要

環状のバームクーヘンを 3 つに分けたい。

バームクーヘンは下図 (問題文から引用) のように N 個のピースに分かれていて、それぞれのサイズは A_{1}, A_{2}, \dots, A_{N} となっている。

バームクーヘンに 3 箇所切り込みを入れて、3 つの連続するピース列に分割する。その 3 つの各ピース列について、それに含まれるピースのサイズの総和を求める。これらの 3 つの総和の最小値として考えられる最大値を求めよ。

スクリーンショット 2018-05-28 10.31.43.png

制約

  • 3 \le N \le 10^{5}
  • 1 \le A_{i} \le 10^{9}

考えたこと

まず「最小値を最大化せよ」という問題なので、全体的な解法としては「二分探索法」が使えそうである。つまり、以下の判定問題を解くことに帰着するのだ。

3 つの部分すべてについて、サイズの総和が x 以上となるようにすることが可能かどうかを判定せよ

この答えが "Yes" となる最大の x を求めれば OK。

判定問題

この判定問題を解くためには、次のデータが欲しい。

  • next[ i ] := 区間 [i, j) の総和が x 以上であるような最小の j

このデータはしゃくとり法によって、 O(N) で求められる！！

qiita.com

このデータを求めておけば、次のように O(N) で判定できる。

  • 最初の切り込み位置 (スタート位置) は全探索する
  • 最初のピースと 2 個目のピース列の切れ目の位置は、next 配列で求められる
  • さらに、2 個目のピース列と 3 個目のピース列の切れ目の位置も、next 配列で求められる
  • 残る「3 個目のピース列」のサイズが x 以上ならば Yes

全体として、二分探索法とを合わせて、計算量は O(N \log S) となる ( S を A の総和とする)。

コード

このような「数珠状の数列」を扱うときには、数列を二週させたもの (長さ 2N) を扱うとやりやすい！

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

int main() {
    /* 入力 */
    int N;
    cin >> N;
    vector<long long> a(N*2); // 環状の数列を扱うときは二週確保はよくやる
    long long total = 0; // バームクーヘン全体のサイズ
    for (int i = 0; i < N; ++i) cin >> a[i], a[i+N] = a[i], total += a[i];
    
    /* 二分探索 */
    long long low = 0, high = 1LL<<60;
    while (high - low > 1) {
        /* 3 ピースとも mid 以上にできるかを判定する */
        long long mid = low + (high - low) / 2;
    
        /* しゃくとり法により、各切れ目から mid 以上になる最小区間がどこまでかを求める */
        vector<int> Next(N, -1);
        vector<long long> Size(N, -1);
        int right = 0;
        long long sum = 0;
        for (int left = 0; left < N; ++left) {
            while (right < N*2 && sum < mid) {
                sum += a[right];
                ++right;
            }
            if (sum >= mid) { // mid 以上なら記録
                Next[left] = right;
                Size[left] = sum;
            }
            if (right == left) ++right;
            else sum -= a[left];
        }
        
        /* check */
        bool ok = false;
        for (int i = 0; i < N; ++i) {
            /* 1 ピース目 */
            int ni = Next[i];
            if (ni == -1) continue;
            if (Size[i] >= total) continue;
            
            /* 2 ピース目 */
            ni %= N;
            int nni = Next[ni];
            if (nni == -1) continue;
            
            // 残りが mid 以上なら OK
            if (total - Size[i] - Size[ni] >= mid) ok = true;
        }
        
        if (!ok) high = mid;
        else low = mid;
    }
    
    cout << low << endl;
}

別解： O(N) でできるらしい

公式 editorial に、二分探索によらない O(N) 解法も載ってる

https://www.ioi-jp.org/joi/2013/2014-ho/2014-ho-t3-review.pdf