はまやんはまやんはまやん

hamayanhamayan's blog

Binary Differences [CSAcademy #71 C]

https://csacademy.com/contest/round-71/task/binary-differences/statement/

N要素のバイナリ列Aがある。
このバイナリ列の連続部分列の「0の個数-1の個数」をコストとする。
全ての連続部分列を考えた時に取りうるコストのパターンは何通りか?
(空の連続部分列も考える)

解法

累積和的な考え方を用いていこう。
「0の個数-1の個数」がコストなので、0が増えるとコスト+1、1が増えるとコスト-1となる。
よって、配列Aの0を1に1を-1に変えておこう。
 
累積和の配列を考える。
B[i] := [0..i]のコスト
これを使うと[i,j]のコストはB[j] - B[i-1]で計算できる。
右端を固定して考えると、[?,j]のコストはB[j] - B[?-1]となる。
ここで右端がjのコストのパターンを考えるとB[0]~B[j-1]の中で最大のものを引くと最小のコスト、最小のものを引くと最大のコストが得られる。
つまり右端がjのコストの範囲は[B[j] - (今までのB[i]の最大), B[j] - (今までのB[i]の最小)]となる。
それに加えてB[i]は1つずつ増減するので、このコストの範囲の数はどれも達成できることになる。
 
これより、以下の変数を更新しながら、答えの範囲を特定していく。
L := 取りうるコストの範囲の左端
R := 取りうるコストの範囲の右端
smL := 今までの累積和の範囲の左端
smR := 今までの累積和の範囲の右端
sm := ここまでの累積和
最後にR-L+1が答え。

int N, A[101010];
int L, R, sm, smL, smR;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) {
        if(A[i] == 0) A[i] = 1;
        else A[i] = -1;
    }
    rep(i, 0, N) {
        sm += A[i];

        chmin(L, sm - smR);
        chmax(R, sm - smL);
        chmin(smL, sm);
        chmax(smR, sm);
    }

    int ans = R - L + 1;
    cout << ans << endl;
}