[Codeforces] Codeforces Round #674 (Div. 3) D. Non-zero Segments

2020年12月12日

問題

方針

AGC 023 A – Zero-Sum Ranges と似ている問題です。\( s \) を \( a \) の累積和として、

\[ s_i = a_1 + a_2 + \cdots a_i \]

とします。また、\( s_0 = 0 \) です。ある部分列の総和は \( s_i – s_j \ ( i < j) \) と計算できます。

前から累積和を計算していき、セットに格納します。すでにセットに存在する累積和があるとき、大きい値を挿入して部分列の総和が \( 0 \) となるものを消します。このとき、大きい値を挿入する前の累積和と以降の累積和が同じ値になることはないので、セットの中身を消去します。また、セットに \( 0 \) を入れて初期化することに注意します。

コード

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

int main() {
    int n;
    cin >> n;
    ll a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    set<ll> s;
    s.insert(0);
    int ans = 0;
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i];
        if (s.count(sum)) {
            ans++;
            s.clear();
            s.insert(0);
            sum = a[i];
        }
        s.insert(sum);
    }
    cout << ans << "\n";
    return 0;
}

感想

コンテスト中に Zero Sum Ranges の解説を見ましたが解けませんでした。この問題の解説を見てちょっとだけ理解できました。