XOR問題でまず使えるようにしたいのは、同じ値を2回XORすると消えるという性質です。この性質が分かると、式から未知の値を取り出す問題と、全体のXORから一つの値を復元する問題を同じ考え方で解けます。
この記事では、入門のABC213 Aで一つの式を変形し、次にABC171 Eで全体XORの再利用へ進みます。どちらも公式の入力形式で動くPython参考コードまで確認します。
XOR問題で最初に覚える3つの性質
XOR（排他的論理和）は、二進数の各桁を比べ、片方だけが1ならその桁を1にする演算です。Pythonでは^を使います。定義と具体例は、ABC213 Aの公式問題文でも確認できます。
x | y | x ^ y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
たとえば3は二進数で011、5は101です。桁ごとにXORを取ると110になり、十進数では6です。
| 値 | 2進数 |
|---|---|
3 | 011 |
5 | 101 |
3 ^ 5 | 110（十進数の6） |
問題を解くときは、次の3つを使います。
- 同じ値同士では
x ^ x = 0になる。 - 0とのXORでは
x ^ 0 = xになる。 - 計算する順序と括り方を変えられる。
この3つを合わせると、同じ値が2回ある部分を隣り合わせにして0へ消せます。以降の2問では、この「同じ値を消す」操作を別の形で使います。
ABC213 A：未知のCをXORで取り出す
ABC213 A – Bitwise Exclusive Orでは、0以上255以下のAとBが与えられ、A ^ C = Bを満たすCを求めます。
足し算の方程式で両辺から同じ値を引くように、XORでは両辺に同じ値をXORします。この導出はABC213 Aの公式解説にも示されています。
A ^ C = Bの両辺にAをXORすると、左辺はA ^ A ^ Cです。A ^ A = 0なのでAが消え、次の式になります。
C = A xor B
公式の入力例A = 3、B = 6を追うと、Cは011 ^ 110 = 101、つまり5です。元の式へ戻すと3 ^ 5 = 6になり、条件を満たします。
A, B = map(int, input().split())
print(A ^ B)この参考コードは、公式の2つの入力例3 6と10 12で、それぞれ5と6を出力することを確認しています。
正しさ：出力をC = A ^ Bとすると、A ^ C = A ^ A ^ B = 0 ^ B = Bです。したがって、出力したCは問題の条件を満たします。
計算量：制約内の整数1組にXORを1回行うため、時間計算量はO(1)、追加メモリはO(1)です。
ABC171 E：全体XORを一度だけ計算する
ABC171 E – Red Scarfでは、偶数N個の未知の値b1からbNがあります。入力のaiは、biだけを除いた全要素のXORです。この情報から全てのbiを復元します。
Nは最大200000です。各iについて「自分以外」を最初から計算すると、要素を約N回ずつ見るためO(N2)になります。そこで、入力全体のXORを一度だけ計算します。
入力全体のXORをSとします。
S = a1 xor a2 xor … xor aN
この式の中で、未知の値bjが何回現れるかを数えます。bjはajには含まれず、それ以外の全てのaiに含まれるため、出現回数はN - 1回です。
問題ではNが偶数なので、N - 1は奇数です。同じ値を偶数回XORした部分は2個ずつ消え、奇数回なら最後に1個だけ残ります。したがって、Sは未知の値全体のXORと一致します。この導出はABC171の公式解説PDF（E: Red Scarf）で確認できます。
S = b1 xor b2 xor … xor bN
さらに、SとaiをXORします。aiにはbi以外の全要素が入っています。Sと重ねると、それらは2回ずつ現れて消え、biだけが残ります。
bi = S xor ai
公式サンプルを手で追う
公式サンプルの入力列は20 11 9 24です。まず全体XORを順に計算します。
| 計算 | 結果 |
|---|---|
20 ^ 11 | 31 |
31 ^ 9 | 22 |
22 ^ 24 | 14 |
Sは14です。各入力とSをXORすると、次の値を復元できます。
| i | 計算 | bi |
|---|---|---|
| 1 | 14 ^ 20 | 26 |
| 2 | 14 ^ 11 | 5 |
| 3 | 14 ^ 9 | 7 |
| 4 | 14 ^ 24 | 22 |
得られた26 5 7 22は公式の出力例と一致します。たとえば1番目を除いた5 ^ 7 ^ 22は20となり、入力のa1へ戻ります。
Python参考コード
N = int(input())
a = list(map(int, input().split()))
s = 0
for x in a:
s ^= x
print(*(s ^ x for x in a))最初のループでSを求め、最後に各aiからbiを作って出力します。この参考コードは公式サンプルを無加工で入力し、26 5 7 22を出力することを確認しています。
正しさ：Sには全てのbjが1回ずつ含まれ、aiにはbi以外が1回ずつ含まれます。S ^ a_iではjがiでない全てのbjが2回になって消えるため、biだけが残ります。
計算量：N個の入力を1回走査し、N個の答えを出力するため、時間計算量はO(N)です。掲載コードは入力列をリストとして保持するため、メモリはO(N)です。
次のXOR問題で見る2つの形
今回の2問から、次の問題で探す形を二つに整理できます。
- 未知の値を取り出す：
既知の値 ^ 未知の値 = 結果という式なら、両側に同じ既知の値をXORできないか考える。 - 一つを除いた値を求める：各位置について最初から計算せず、全体XORを一度作り、対象の値をもう一度XORして消す、または戻す。
一方、ABC126 F – XOR Matchingは、各値を2回含む列そのものを作り、等しい値の間のXOR条件も満たす問題です。一つの未知数を取り出すだけではなく、解が存在するかと、どの順番に並べるかを分けて考える必要があります。今回の2問を説明なしで実装できるようになった後の発展問題として読むと、難しさの違いが見えます。
コードを見る前に式を1行書く
まずABC213 Aを、参考コードを隠してC = A ^ Bまで自分で導いてみてください。次にABC171 Eの公式サンプルで、Sと各biを紙に書いてから実装します。
式を先に書くと、コードのs ^= xが単なる書き方ではなく「全体XORを作る処理」で、s ^ xが「同じ値を消して必要な値を残す処理」だと対応づけられます。この対応を説明できれば、別のXOR問題でも使う性質を選びやすくなります。
