Quiz
https://atcoder.jp/contests/qupc2018/tasks/qupc2018_e
Submit
https://atcoder.jp/contests/qupc2018/submissions/4183484
定義
- 入力A (配列)
- 累積和Ac (配列)
- 部分和が0になる個数 Za (配列)
解法
- 累積和を求める
- 累積和の中に同じ数が出現したら、A上では部分和=0となる
- iを進めながらmapでカウントしつつ i-1 の結果も利用してZaを埋める
- DP? imos?
- それは意識していなかったが、O(N)で求めようとすると自然とそうなる
- Aを逆向きに見た場合も同様に
- 累積和
- 部分和0の個数配列
- を求める
- 最後にi (変更点・断絶の壁）を変えつつ、壁の左右の「部分和0の個数」を求めて和を取る
- その中の最小値が答え
計算量
- 累積和O(N)
- Zaも線形に求まってO(N)
- 全体でO(N)
注意点
- 累積和Ac[-1] = 0と考えるべき
- 累積和の中ではじめて0が出たとき、Aでの部分和0が存在する
先に解いておくべき問題
- zero sum ranges
