コイン遊び [yukicoder 1183]

https://yukicoder.me/problems/no/1183

解説

https://yukicoder.me/submissions/536748

区間swapを行ってA=Bにしたいという問題である。
ここで区間操作に関するテクを使用する。

「区間操作は階差数列を取ることで2点要素更新に帰着させることができる」

類題をやったことがないと割と難しいかもしれないが、
今回のような01での区間swapはxorでの階差数列を取ると2点要素更新として帰着可能。
まず、以下のような配列を作る。

1. 事前に配列A,Bの先頭に0を入れておく
2. 配列C,Dを以下のルールで作成する

C[i] = A[i] xor A[i + 1]
D[i] = B[i] xor B[i + 1]

このルールで階差数列を作成すると、A=Bが成り立つこととC=Dが成り立つことは同値関係にある。
xorを取ると隣接要素が同じなら0で、異なるなら1となるので、先頭がどちらも0であることは保証されているので、
差分関係がすべて同じであるなら、元の配列を同一となる。

階差にすると、2点要素更新になるのか？

例えばA[L]からA[R]の要素を変更することを考えると、階差数列への影響は、

• A[L-1]とA[L]が同じであるかの関係が反転 → C[L-1]が変わる
• A[R]とA[R+1]が同じであるかの関係が反転 → C[R]が変わる

のように2点のみ影響を受ける。
そして、この2点は自由に選べるので、配列C,Dの異なる部分の個数を数えて、基本的にはそれを2で割った数が答えになる。
場合によっては異なる部分の個数が奇数になるが、その場合は配列の末尾を指定することで1点変更とできるので、実際は2で割った切り上げが答え。

int N, A[1010101], B[1010101];
int C[1010101], D[1010101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 1, N + 1) cin >> A[i];
    rep(i, 1, N + 1) cin >> B[i];

    rep(i, 0, N) C[i] = A[i] ^ A[i + 1];
    rep(i, 0, N) D[i] = B[i] ^ B[i + 1];

    int diff = 0;
    rep(i, 0, N) if (C[i] != D[i]) diff++;
    int ans = (diff + 1) / 2;
    cout << ans << endl;
}