https://yukicoder.me/problems/no/1183
解説
https://yukicoder.me/submissions/536748
区間swapを行ってA=Bにしたいという問題である。
ここで区間操作に関するテクを使用する。
「区間操作は階差数列を取ることで2点要素更新に帰着させることができる」
類題をやったことがないと割と難しいかもしれないが、
今回のような01での区間swapはxorでの階差数列を取ると2点要素更新として帰着可能。
まず、以下のような配列を作る。
- 事前に配列A,Bの先頭に0を入れておく
- 配列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]の要素を変更することを考えると、階差数列への影響は、
のように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; }