はまやんはまやんはまやん

hamayanhamayan's blog

Splitting Pile [AtCoder Regular Contest 078 C]

http://arc078.contest.atcoder.jp/tasks/arc078_a

解法

http://arc078.contest.atcoder.jp/submissions/1421601

カードの境界線を全探索すればよいのだが、すぬけくんとアライグマが取るカードの総和を求めているとTLEする。
累積和を使う方法もあるが、順番に境界線を探索するときは差分だけ更新する方法の方が簡単である。
x = [0,i]の総和
y = [i+1,N-1]の総和
であるとき、次のx,yは
x' = [0,i+1]の総和 = x + A[i + 1]
y' = [i+2,N-1]の総和 = y - A[i + 1]
であるため、これを順番にやっていき、abs(x - y)の最小値を答える。

#define INF 1LL<<60
typedef long long ll;
int N, A[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
 
    ll x = 0, y = 0;
    ll ans = INF;
    rep(i, 0, N) y += A[i];
    rep(i, 0, N - 1) {
        x += A[i];
        y -= A[i];
        ans = min(ans, abs(x - y));
    }
    cout << ans << endl;
}