Codeforces Round #628 (Div. 2) - D. Ehab the Xorcist - Senの競技プログラミング備忘録

codeforces.com

概要

0 <= u, v <= 10^18のuとvが与えられる。次の条件を満たすような最短の数列を構築しなさい。ただし、複数の構築法があるのならば、そのうちの1通りを出力しなさい。存在しない場合は-1を出力してください。

数列の要素のXORがuと等しく、和がvに等しい

ACするまで

1. まず、できなさそうなのを条件ではじく。
2. 和とXORの定番の関係式で考えてみると、長さはたかだか3で収まるとわかる。
3. 長さが2で収まるにはどうすればいいのか？を考えると、条件が分かるので、書いてAC!

考察

XORの問題はパズル要素高めと言われているが、過去問をしっかり解けば、取れる定石というのがいくつかわかってくる。

今回の場合は、ひとまず作れないのはどのような場合か？を考える。
まず、

$a+b=a \oplus b + 2(a 論理積 b)$ という関係

から、u >= vとなってるものは、どう頑張っても作れないとわかる。

次に、

XORと相性がいいmod 2、つまり偶奇でも考える。

uが奇数で、vが偶数の時、「奇数個の奇数をXORしても偶数になれない」
uが偶数で、vが奇数の時、「奇数個の奇数を足しても偶数になれない」

という事実から、uとvの偶奇が一致しないものは構築できない、とわかる。

さて、残りのものはすべて構築できるか？というと、実は可能である。

XORの典型操作としてあるのは、

$a \oplus a = 0$ 　2回同じもののXORは0(単位元)になる！

というのがあるが、今回もこれを使う。

実は、v>=uで、vとuの偶奇は一致するから、{u, (v-u)/2, (v-u)/2}という数列は、問題の条件を満たす。(同じもの同士のXORを利用して、和だけ増加させてXORには変動を与えない)

これで、長さ3の数列ならばできる！とわかった。では、長さ2でできるのはどのような場合なのだろうか？

$a+b=a \oplus b + 2(a 論理積 b)$ の式を思い出そう。今は2要素を考えているのでばっちりである。この式を満たすaとbが存在するのならば、長さ2の数列が作れる。

$\frac {v-u}{2}=(a論理積b)$ という式が成り立つので、これは
(v-u)/2の立ってるbitは、aもbも立たないといけない。

この時、 $a \oplus b = u$ のuで立ってるbitに関しては、必ずaとbのうちの一方だけ立ち、もう一方が立たない、を満たさないといけないが、これがさきほどの「(v-u)/2の立ってるbitは、aもbも立たないといけない。」の条件と衝突をしてしまうと、そのような $a, b$ は存在しないということになる。