phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

AGC023 A. Zero-Sum Ranges

問題

長さNの整数列Aの連続部分列について総和が0になるものの個数(位置が異なる場合は別カウント)を求めよ。

制約

  • 1 <= N <= 2*10^5
  • -10^9 <= A_i <= 10^9

解法

小さいケースで考えてみる。A={a,b,c}。
よくある手として、要素cで終わる連続部分列{a,b,c}, {b,c}, {c}の総和が0になるものを求めるときに、そこまでの計算結果をメモっておいてそれを使って高速に求める方法がある。

f:id:phyllo_algo:20180429132042p:plain

連続部分列を書き出してみると、上のような図になっている。
要素cで終わる連続部分列は緑で描かれている範囲で、この3つの連続部分列を見てみると、一番下のSc=a+b+cは累積和なので、順次求めていけるが、上の2つをどう処理するかが問題になっている。


よく観察すると、SaやSbが求められていたとすると、要素cで終わる連続部分列の総和は、その時点での累積和Scからそれ以前の累積和Sa,Sbを引いたものになっている。Sc, Sc-Sb, Sc-Sa。

この性質を使えば、その地点以前の「累積和とその個数」をmapなどでメモしておき、その地点での値xを加えたら0になるものの個数=メモの中にある-xの個数、を順次求めていけばよい。
計算量は、mapを使う場合は、O(NlogN)程度。