QUPC2018-E:Treeone
最近よく見るやつ。
問題概要
長さの数列が与えられる。その数列の連続する部分列であって,総和が0であるものの個数を数列のたぴさと呼ぶ。数列のうち1つの値を自由に変えられるとき,あり得るたぴさの最小値を求めよ。
E - Treeone
解法
「数列の連続する部分列であって,総和が0であるものの個数」と聞いたら,累積和を考えるのが定石である。その個数は,となるの組の個数に等しい。つまりは,ある条件を満たす区間の数である。このうち,の値を一つだけ変えて,どれだけそういう区間を減らせるかということを考えよう。答えは
- 「元の数列のたぴさ」から「を変えることで減らせる区間の数の最大値」を引いたもの
である。「元の数列のたぴさ」の効率的な計算については,A - Zero-Sum Rangesがそのものなので参照していただきたい。
の値をうまく変えることによって,を満たす区間については,条件を満たさないようにできる。例えば,を5000兆とかにすれば,もともと和が0だった区間の和が5000兆くらいになる。また,を5000兆に変えたことによって,和が0でなかったの区間の和が0になることもない。を含む区間については5000兆という数字がでかすぎて和が0になりようがないし,を含まない区間はが5000兆になったところで何の影響もない。よって,各について,「を満たす区間であって,なるものの個数」が効率的に求まればよい。
これにはimos法と呼ばれるものを使う(imos法を知らない方は調べてください)。各について,「から始まる条件をみたす区間の数」足し算し,「で終わる条件をみたす区間の数」を引き算する。その後,順に累積和を取っていけば,各に対して,「を含む条件をみたす区間の数」がわかる。また
よって,各の値が全部でいくつあるかを調べておき,が小さい順に上の計算をしてけばよい(詳細はコードを見た方がわかると思う)。実装上注意すべきは,単にとなるような場合(つまり,となる場合)を数えるために,から計算を行うところである。
提出
https://beta.atcoder.jp/contests/qupc2018/submissions/3441083
- がどんな値かわからないため,mapを用いている
- 「であって,をみたすものの個数」や「であって,をみたすものの個数」は適当に引き算すれば求まるので,直接調べる必要はない
方針はすぐだったが,変なところでバグらせて足を引っ張ってしまった。反省。