[ABC233] D - Count Interval

[Q] https://atcoder.jp/contests/abc233/tasks/abc233_d

1. DP[val] = 何通りあるか、で状態遷移を管理。
indexを動かすごとに、全部のDP[val]を、DP[val+a]に更新するとO(N^2)になっちゃう。
2. 何か基準値を更新し、状態遷移の復元ができるようにすればいい。O(NlogN)になるはず。
3. しかし！！！そのアウトラインはとうに分かっているのに、脳がパンク(2WA)

この類題4回目くらいだと思うけど、なぜ解けないのだろう！くやしい！なんてだらしないんだ！

1. 状態遷移ごとに、既存のDP[val]すべてに、DP[val+a]の更新をすると​

処理数は、1 + 2 + 3 + ... になるのがわかる。O(N^2)
2. これを、++DP[-累積和] で保存し、+累積和で復元すればO(N)

累積のvalがとても大きくなる可能性があるので、hashでもつため、map管理。O(NlogN)になる。

実装

int main(){
 cincout();
 
 ll N, K;
 cin >> N >> K;
 map<ll, ll> M;
 
 ll ans=0;
 ll sum=0;

 // 初期状態
 M[0] = 1;
 
 rep(i, N){
   ll a;
   cin >> a;
   sum += a;
   if (M.count(K-sum)) ans+=M[K-sum];
   ++M[-sum];
 }
 cout << ans << endl;
}

Q. count
A. returnは0か1。存在するなら1。valを返すわけではないので注意。

https://atcoder.jp/contests/abc233/submissions/28140169