B - Count 1's - 予鈴

問題

長さ $N$ の数列 $A$ が与えられる。
$A$ の連続する部分列を一つ選び、これを一度flipする。
スコア $S$ を $A$ に含まれる1の個数とするとき、 $S$ の取りうる値が何通りあるか求めよ。

考えたこと

・答えの候補はたかだか $N$ 程度なので、全部試せる
・最大値さえわかれば良さそう
・どうやって最大値求めるんだ…？

解法

まず方針として、1の個数を最大にできる場合と、1の個数を最小にできる2つがわかれば良い。
変化量だけ考えればよいという感じ。 $[l,r]$ をflipしたときに、1の数が増える/ 減る分の $\Delta m$ だけを考えるという感じ。つまり、flipしたところ・しなかった部分をわざわざ数え上げる必要はない。これも思いつけませんでした。

この $\Delta m$ は累積和を用いると高速に求めることができる。
まずはじめに、flipするという操作を言い換えると、1→0 ,0→1となるなので、元の数列 $A$ に対して、1 → -1, 0→ +1　とした数列 $A'$ を考えて、累積和を計算する。

このままだとただの累積和で、 $[l,r]$ を指定することで、その区間をflipしたときの1の数が $O(1)$ でわかるが、制約から $[l,r]$ を全探索はできない。

ここで、 $r$ のみを全探索して効率的に求める方法を考える。
累積和の配列を $csum$ とすれば、 $csum [r]$ は0から $r$ までの和となる。
問題は、 $csum[r] - csum[l]$ が最大となる $l$ を探し出したい。
これは、 $l$ は $r$ より前に現れているはずなんで、 $p < r$ で $csum[p]$ が最も小さいものを記録しておけば良い。

最小値も同様。

感想

(~~解説に1 の個数を最小/最大で何個にできるか，は簡単に求まりますとあるが、自分にとっては簡単ではなかった~~)
難しいと思う。ちなみに公式の紙の解説よりも、ビデオのほうがわかりやすい。

最大値と最小値の間の値はすべて取れるのか、というのも考える必要があるが、これは自分の場合は素直に理解できた。グラフを書くとなめらかになるので、その間の数字は全部取れるだろ、みたいな。

#include <iostream>
#include <vector>

using namespace std;

using Int = long long;

int main()
{
    Int N; cin >> N;
    vector<int>A(N);
    
    for(auto& e : A)
        cin >> e;
    
    int maxm = 0, mini = 0;
    int prevMax = 0, prevMin = 0;
    
    int csum = 0;
    for(auto cur : A)
    {
        csum += (cur == 0 ? 1 : -1);
      
        maxm = max(maxm,csum - prevMin);
        mini = min(mini,csum - prevMax);
        
        prevMin = min(prevMin, csum);
        prevMax = max(prevMax, csum);
        
    }
    
    cout << maxm - mini + 1 << endl;
}