AOJ 0600 Baumkuchen

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0600

解法

累積和と二分探索．
まず，バウムクーヘンの累積和を二周分求めておく．
その後，左端を適当に定め，そこから始めて長さが (lb + ub) / 2 以上になるところを2分探索で求める．さらにそこから同様に次の地点を求めて，各地点の距離の差が(lb + ub) / 2以上であれば，下限を更新する．そうでなければ上限を更新．

解の範囲を収束させるのに O(logN)，仮定した長さが条件をみたすか調べるのにO(NlogN)かかるので，トータルO(N(logN)^2)．

しゃくとりでやるともうちょい早くなりそうだけどめんどくさそうなのでやめました（実はそんなにめんどくさくない？）

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
bool check(vector<ll> const& a, ll m) {
    const int N = a.size() / 2;
    bool ok = false;
    for(int i=0; i<N; ++i) {
        int j = lower_bound(a.begin()+i, a.begin()+i+N+1, a[i]+m) - a.begin();
        int k = lower_bound(a.begin()+j, a.begin()+i+N+1, a[j]+m) - a.begin();
        if(a[j] - a[i] >= m && a[k] - a[j] >= m && a[i+N] - a[k] >= m) {
            ok = true;
            break;
        }
    }
    return ok;
}
 
int main() {
    int N;
    cin >> N;
    vector<ll> a(2*N+1);
    for(int i=1; i<=N; ++i) {
        cin >> a[i];
        a[i+N] = a[i];
    }
    for(int i=1; i<2*N+1; ++i) {
        a[i] += a[i-1];
    }
 
    ll lb = 0, ub = (a[N] + 2) / 3;
    while(ub - lb > 1) {
        ll m = (ub + lb) / 2;
        if(check(a, m)) {
            lb = m;
        } else {
            ub = m;
        }
    }
    cout << lb << endl;
}