AGC023 A 考察

AGC023 A - Zero-Sum Ranges

解説 AC 。

考えたこと。先頭と末尾の位置を決めてその間の和が 0 になる個数なので O(N^2) で良いなら累積和をとって二重ループで OK 。ただし N <= 2 * 10^5 なので今回は間に合わない。ここまでで諦めた。

解説から理解したこと。和が 0 になる箇所を求めるために累積和を使うところまでは正しい。和が 0 になるということは S[r] - S[l] = 0 になる。つまり S[l] = S[r] にできる場合の数を求めれば良い。ここに気が付かなかった。 S を走査して S[i] の出現回数を数えて 2 以上なら x choose 2 = x * (x - 1) / 2 の和を求める。

https://atcoder.jp/contests/agc023/submissions/15875206

リングフィットアドベンチャーを続けている。体調が万全でないためややつらい。

bouzuya/rust-memo 。 obsoleted by と linked by を追加している。まだ使いにくい。

『となりのトトロ』を観た。前回は 2016-11-04 。前に子どもに見せたときは飽きてしまったのだけど今回は最後まで観ていた。