AtCoder Grand Contest 023 A - Zero-Sum Ranges

点問題最強といわれたZero-Sum Rangesを倒しましょう

問題概要

atcoder.jp

長さの数列の中で、和がになる区間はいくつあるか。ただし値が同じでも位置が違うなら異なるものとする。

例）






このつの区間の和はそれぞれになるので、この場合出力する答えはになります。

考察

の最大値はなので、愚直に探索してはになってしまい間に合いません。

区間和を扱うには累積和が便利なので累積和を使いましょう。

累積和をとった時に和がになる区間はどうなるのかというと、累積和の値が等しくなります。

ということは、まず累積和をとったあとに各値がいくつあるのかを数えます。

そして区間の数ということは、その同じ値の中からつを選ぶ場合の数なので、各値の数をとすると、各値のの総和が答えとなります。

そして、はでも求められるのですが、これはまた ~ の総和でもあるので、以下のように実装することも出来ます。

long long ans = 0;
map<long long, int> m;
//累積和をとった0項目は0とするので加算する
m[0]++;

for(int i = 1; i < n + 1; i++){
    //出てくるを数える前に答えに加算する
    ans += m[a[i]];

    //出てくる数を数える
    m[a[i]]++;
}

を使って各値が出てくる回数を数えるのですが、回出てきた値に対して ~ の総和を求めるので、先に答えの変数に出てきた数を加算してから出てくる数を数えることで、上手に ~ の総和を求めることが出来ます。

実装

よって今までのことを実装すると以下のようになります。

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

int main()
{
    int n;
    cin >> n;
    long long ans = 0;
    vector<long long> a(n+1);
    map<long long, int> m;
    //累積和をとった0項目は0とするので加算する
    m[0]++;
    for(int i = 1; i < n + 1; i++){
        cin >> a[i];
        //累積和をとる
        a[i] += a[i-1];
        //出てくるを数える前に答えに加算する
        ans += m[a[i]];
        //出てくる数を数える
        m[a[i]]++;
    }
    cout << ans << endl;
}

先ほどの方法でを求めたので、入力と同時に累積和をとりながら答えも求めることが出来ました。