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

hamayanhamayan's blog

XOR Replace [AtCoder Grand Contest 016 D]

http://agc016.contest.atcoder.jp/tasks/agc016_d

解法

http://agc016.contest.atcoder.jp/submissions/1365639

www.youtube.com
解説放送の副読本として書きます。

一回の操作は配列とそのxor和とのswapに相当する。
これは解説放送の通り。

そのため、それぞれxor和を取って、multisetとして同じとなるかを判定して、同じでないなら-1で終了する。
(chk関数)

もし、2つのxor和が同じでない場合は最初にswapしておく。
これで解説放送45:30頃から出てくる図形と同じような状況になる。

これで各配列で異なっている要素を連結させていくのだが、普通にunionfindすると[0,10^9]となってしまうので、座圧して管理する。
2つの配列の同じ添字で合ってない個数をe, 連結成分の個数をcとする。
すると、答えはe + cとなるのだが、場合によっては1回分得をする場合がある。
rngさんも解説放送中に言っているが、「サイクルにxor和が含まれる場合」である。
これを判定しておき、もし含まれるならば、1回分減らす。
これで50:00頃から出てくる数式が答えとなる、e+c or e+c-1