AtCoder Grand Contest 023
0完太陽でした. 悲しいね.
A - Zero-Sum Ranges
以下の提出と公式editorialを参考に解きなおした.
https://beta.atcoder.jp/contests/agc023/submissions/2426038
editorialの解説は読んだらわかったけどなんでこんなコードになるのかしばらくわからなかった.
combination(nCk)を使わなくてもretにmp[sum]の値を逐次足していけば同様の計算になるってことだと思う(自信なし).
#include <bits/stdc++.h> using namespace std; int main(void) { int n; cin >> n; map <long long, int> mp; long long sum = 0; mp[0]++; long long ret = 0; for(int i = 0; i < n; i++) { // cout << "i: " << i << endl; // cout << "sum: " << sum << endl; // cout << "ret: " << ret << endl; int x; cin >> x; // cout << "a[" << i << "]: " << x << endl; // cout << "-------------------------" << endl; sum += x; ret += mp[sum]; mp[sum]++; } cout << ret << endl; }