AtCoder Grand Contest 016: D - XOR Replace

AtCoder AGC AGC #016 問題記録

https://atcoder.jp/contests/agc016/tasks/agc016_d

問題概要

長さNの数列A, Bが与えられる。Aの要素をひとつ選びその値をAのすべての要素のXORで置き換えるという操作を好きなだけ行えるとき、AをBに一致させることができるか判定せよ。また可能な場合には最小の操作回数も求めよ。

N <= 105

解法

初期状態でのA全体のXORを仮にXと置く。このときXOR演算の性質から、仮にA[2]をXで置き換えたあとのA全体のXORはA[2]になる( x xor y xor z = w <=> w xor y xor z = x )。よって次にA[3]を選んだ場合、A[3]は初期状態のA[2]と置き換えられる。そして今度はA[3]がA全体のXORになる。このように、一度操作を行うとそのとき選んだ要素が次の「A全体のXOR」になるということがわかる。

なのでこの問題で行っている操作は結局単純なswapであるといえる。つまり初期状態でのA全体のXORをAの末尾にくっつけた数列A'を考えたとき、A'において末尾以外の要素と末尾をswapしているのとまったく同じことである。単なるswapなので当然操作の過程で新たな数が登場したりすることもない。よって一致可能性判定はかなり簡単にできて、Bに対しても末尾に全体のXORをくっつけた数列B'を考えたときにA'とB'の構成要素が同じかどうかを見ればよい。

これで一致させられるかどうかの判定はできたので、あとは最小操作回数を求めることになる。先程言い換えたようなswap操作で考えると、効率の良い一致のさせ方は「今の末尾にある数を、それを必要としている場所に送り込む -> 新たに末尾に入ってきた数を、それを必要としている場所に送り込む -> ...」という風に、玉突き的に値がずれていく感じの操作になる。別の言い方をすると、好きな順番でいくつかの要素（末尾は必ず含む）を選択し、選択した順で値をcyclic shiftさせるような操作をすると、最低限の操作回数で複数の値を一気に一致させることができる、ということになる。ただしこのとき注意しなくてはいけないのが「末尾は必ず含む」のところで、末尾の値が必要なかったとしても必ずシフトに巻き込まれることになってしまい、1回分余計に操作をする必要が生じる。以下で具体例を見ていく。

たとえばA'が{1, 2, 3, 0}でB'が{2, 3, 1, 0}だったとき、操作は {1, 2, 3, 0} -> {1, 2, 0, 3} -> {1, 3, 0, 2} -> {2, 3, 0, 1} -> {2, 3, 1, 0} と4回になる。{2, 3, 0, 1}の時点でcyclic shiftが完了しているのだが、末尾の0はもともとずれていた数の集合{1, 2, 3}には含まれていないので、それを元の位置に戻すために操作を+1回行っている。n個の要素のcyclic shiftには(n-1)回の操作が必要で今回はさらに+1回操作をしているため、結局4回の操作になった。

一方で{1, 2, 3}を{2, 3, 1}に一致させることを考えると、これは {1, 2, 3} -> {1, 3, 2} -> {2, 3, 1} と2回で済む。これは末尾の数が必要とされていたためで、このような場合はcyclic shiftを1回やるだけで各要素がぴったりはまるので、操作は(n-1)回で済む。

また別のパターンの例としてA'が{1, 2, 3, 4, 5, 1}でB'が{2, 3, 1, 5, 4, 1}のときを考える。このとき明らかに (1, 2, 3) と (4, 5) は別々にcyclic shiftを行っていくべきで、(1, 2, 3)の方は末尾の1のおかげで最後の合わせ+1回が必要ないが、(4, 5)の方は最後の+1回が必要となる。

上のようなパターンだと見て明らかに(1, 2, 3)と(4, 5)は別だとわかるが、一般的に解くためにはもう少し定式的にやる必要がある。どのようにやるかというと、A[i]!=B[i]となるiがあったとき、A[i]とB[i]をそれぞれグラフの頂点番号とみなして(A[i], B[i])間に辺を張ることにする。これをA', B'のすべてのi(0 <= i <= N)に対して行って出来たグラフにおいて、同じ連結成分内に属するものの集合をひとつのcyclic shiftの単位とみなすことができる（詳しい話は公式解説等参照）。連結成分だけが問題であるので実際にはグラフをつくる必要はなく、UnionFindとかで連結成分を管理すればよい（頂点番号が大きくなりうるので座標圧縮的なテクであらかじめ値を潰しておくとかはする必要がある）。

各連結成分内で必要な操作回数は、上で述べたように末尾の数を必要とするかどうかによって違いがあり、もし末尾と関わりのない連結成分であれば(要素数+1)回かかる。なおここでいう要素数はUnionFindで持ったときの要素数ではなく、その連結成分にA[i]が含まれており、かつA[i]!=B[i]であるようなiの数であることに注意する（グラフをつくる段階で同じ値の要素をひとつの頂点に潰してしまっているのでここは一致しない）。末尾と関わりのあるような連結成分であれば+1が必要なく単に要素数回の操作になる。ただしこのときA'の末尾!=B'の末尾であれば、それは要素数に含めなくてよい。なぜならここが等しくてもそうでなくても必ずcyclic shiftには巻き込まれるからで、さらに連結成分の性質からcyclic shiftの結果どちらにせよB'の末尾に等しい値が移動してくることがわかっているからである。

以上をまとめると、結局A[i]!=B[i]であるような箇所は末尾を除いて答えに+1の寄与があり、さらに末尾と関わりのない連結成分の数だけ余計な操作が+1されるので、この数をかぞえて足せば答えとなる。

感想

今回ばかりは本当に意味のわからない文章を書いてしまった手応えがあるので自分が解くとき参考にしたリンクを張りまくって逃げます

http://kmjp.hatenablog.jp/entry/2017/06/25/0900

https://camypaper.bitbucket.io/2017/06/20/agc016d/

https://www.hamayanhamayan.com/entry/2017/06/19/185428

https://kimiyuki.net/writeup/algo/atcoder/agc-016-d/

https://www.youtube.com/watch?v=kdQtQSgIYPI (解説放送)

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.string;

void main() {
    auto N = readln.chomp.to!int;
    auto A = readln.split.map!(to!int).array;
    auto B = readln.split.map!(to!int).array;

    A ~= A.reduce!((a,b) => a^b);
    B ~= B.reduce!((a,b) => a^b);

    if (A.dup.sort() != B.dup.sort()) {
        writeln(-1);
        return;
    }

    auto C = A.dup.sort().uniq.array;
    int M = C.length.to!int;

    int[int] D;
    foreach (i; 0..M) {
        D[C[i]] = i;
    }

    A.each!((ref a) => a = D[a]);
    B.each!((ref a) => a = D[a]);

    auto uf = new UnionFind(M);
    foreach (i; 0..N+1) {
        if (A[i] != B[i]) {
            uf.unite(A[i], B[i]);
            uf.edge[uf.find(A[i])] += 1;
        }
    }


    int ans = 0;

    foreach (i; 0..M) {
        if (uf.find(i) != i) continue;
        if (uf.edge[i] == 0) continue;
        if (uf.find(A.back) == i) {
            ans += uf.edge[i];
            if (A.back != B.back) ans -= 1;
        } else {
            ans += uf.edge[i] + 1;
        }
    }

    ans.writeln;
}



class UnionFind {
    int N;
    int[] table;
    int[] edge;

    this(int n) {
        N = n;
        table = new int[](N);
        fill(table, -1);
        edge = new int[](N);
    }

    int find(int x) {
        return table[x] < 0 ? x : (table[x] = find(table[x]));
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (table[x] > table[y]) swap(x, y);
        edge[x] += edge[y];
        table[x] += table[y];
        table[y] = x;
    }
}