AGC023 A - Zero-Sum Ranges

問題ページ
A - Zero-Sum Ranges

考えたこと

• 問題を読むと200点に見えないので真面目に考える
• とりあえず累積和を取ってみる
• i番目を左端とする区間で部分和が0になる区間はa[i]=a[j]となる
• したがってiより右でa[i]と等しいものの数を数える
• mapで現れた頻度を持ちながら右から見ていくとi番目を左端とする区間で条件を満たすものの数がわかる

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;
  cin >> n;
  VI a(n);
  REP(i, n) cin >> a[i];

  VI b(n);
  b[0] = a[0];
  FOR(i, 1, n) b[i] = a[i] + b[i-1];

  int ret = 0;
  map<int,int> mp;
  for(int i=n-1; i>=0; --i) {
    ret += mp[b[i]];
    // b[i]の個数
    mp[b[i]]++;
  }
  cout << ret+mp[0] << endl;

  return 0;
}