問題概要

$N$ 個の整数からなる数列 $a_{1}, a_{2}, \dots, a_{N}$ が与えられる。これを左右に 2 つに分ける（左右ともに 1 個以上はとる）。

左側の要素の総和を $x$ 、右側の要素の総和を $y$ とするとき、 $|x - y|$ の最小値を求めよ。

制約

$2 \le N \le 2 \times 10^{5}$
$-10^{9} \le a_{i} \le 10^{9}$

考えたこと

もし計算時間を考えなくて良いならば、「左側の要素を何個にするか」で全探索する方法が考えられるだろう。探索候補は $O(N)$ 通りある。そのそれぞれについて、左右の総和を愚直に計算すると $O(N)$ の計算量を要するので、全体として $O(N^{2})$ の計算量となる。このままでは TLE してしまうので、高速化しよう。

まず、左側の総和については、それを表す変数 sum を用意しておき、左側の要素の個数を増やす度に sum に加算していくようにすればよい。

右側の総和については、あらかじめ数列全体の総和 sum_all を求めておけば、sum_all - sum によって求められる。

この方法によって、「左側の要素の個数」を決めたときの、左右の総和を求めるのは $O(1)$ の計算量でこなせるので、全体として $O(N)$ の計算量となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    long long all_sum = 0;
    vector<long long> a(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        all_sum += a[i];
    }

    long long res = 1LL << 60, sum = 0;
    for (int i = 0; i < N - 1; i++) {
        // a[i] までの和
        sum += a[i];

        // もう片方の総和
        long long other = all_sum - sum;

        // diff を更新
        res = min(res, abs(sum - other));
    }
    cout << res << endl;
}

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

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

AtCoder ABC 067 C - Splitting Pile (5Q, 茶色, 300 点)

問題概要

制約

考えたこと

コード