ピザ [第四回 アルゴリズム実技検定 I]

https://atcoder.jp/contests/past202010-open/tasks/past202010_i

前提知識

• 累積和
• 三分探索

解説

https://atcoder.jp/contests/past202010-open/submissions/21472485

様々な実装方法がある。
多分尺取り法でも解けるが、自分は三分探索を利用した。

何をするか

中々方針決めが難しいと思うが、基本は全探索なので、それから考える。
考えるすべての状況を考えてみると、
食べるピースの区間の左端×そこから食べるピースの個数
ですべての状況を表現できることが分かる。
これは4*10¹⁰通りなので、これを試すのは難しい。
この最適化を考えてみよう。

食べるピースの区間の左端だけを全探索する

セクション名にあることを行う。
食べるピースの区間の左端を固定して、食べるピースの個数を1から順番に増やして性質を見てみる。
増やせば増やすほど、Xが増えてYが減ることになる。
abs(X-Y)にこれを当てはめてみると、グラフ的には下に凸な関数として表現できる。
今回求めたいのは値の最小値なので、下に凸な関数の最小値といえば三分探索だ。

最終的には

食べるピースの区間の左端を固定して、食べるピースの個数を三分探索してabs(X-Y)の最小値をそれぞれ求めてその最小値を答えとする。
三分探索の過程で区間の総和を取る必要があるが、これは累積和を使って高速にとってこよう。
あと、実装を簡単にするために、このようなループの性質があるものは、配列aのサイズを2倍にして、同じ内容を後ろに追加しておく。
これで、ループであっても普通に区間で扱うことができる。

これらの要素を丁寧に組み合わせて答える。
答えは10⁹を超えるので型には気を付けること。

int N; ll A[401010];
//---------------------------------------------------------------------------------------------------
ll tot = 0;
int st;
ll f(int len) {
    ll X = A[st + len - 1];
    if (st) X -= A[st - 1];
    ll Y = tot - X;
    return abs(X - Y);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) tot += A[i];
    rep(i, 0, N) A[i + N] = A[i];
    rep(i, 1, N * 2) A[i] += A[i - 1];
    
    ll ans = infl;
    rep(_st, 0, N) {
        st = _st;
        int opt = findMin(1, N + 1, f);
        chmin(ans, f(opt));
    }
    cout << ans << endl;
}