ferinの競プロ帳

競プロについてのメモ

AOJ0600 バームクーヘン

問題ページ
バームクーヘン | Aizu Online Judge

考えたこと

最小値の最大化と言われたので二分探索。判定がO(f(n))であればO(f(n)log(max(A_i)))となる。始点を一箇所固定すればmid以上の最小となるように2箇所切っていくのが最善になる。全パターン確認すれば判定できるのでO(n^2)かけていいなら簡単。判定をO(nlogn)とかO(n)でできれば解けそう。累積和を取っておいて二分探索すれば各始点についてO(logn)で判定できそうなので全体でO(nlognlog(max(A_i)))で解けそう。
累積和が明らかにintに収まる範囲内ではないのでlong longを使う。円環を扱うときは二周分とっておくと実装が楽。

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int n;
ll a[200010], b[200010];

bool check(int m) {
  REP(i, n) {
    int tmp = i==0 ? 0 : b[i-1];
    int itr1 = lower_bound(b+i, b+i+n, tmp+m) - b;
    int itr2 = lower_bound(b+i, b+i+n, b[itr1]+m) - b;
    if(b[n+i-1] - b[itr2] >= m) return true;
  }
  return false;
}

signed main(void)
{
  cin >> n;
  REP(i, n) cin >> a[i];
  FOR(i, n, 2*n) a[i] = a[i-n];
  b[0] = a[0];
  FOR(i, 1, 2*n) b[i] = a[i] + b[i-1];

  // [low, high)
  ll low=1, high=b[n-1];
  while(high-low>1) {
    ll mid = (low+high)/2;
    if(check(mid)) {
      low = mid;
    } else {
      high = mid;
    }
  }
  cout << low << endl;

  return 0;
}