XOR の代数的性質とか

$\newcommand{\xor}{\mathbin{\small \triangle}}$どうも, ビット演算が好きなたぬきです。

今回は XOR がもつ特徴的な性質をまとめ, それを利用した競プロの問題を紹介していきます。

以降, XOR の中置演算子として $\xor$ を使用します。

XOR の性質

では XOR の代数的性質を並べていきます。 比較用として加法と乗法も並べます。

1. 可換である。
   $a \xor b = b \xor a$

2. 結合律を満たす。
   $(a \xor b) \xor c = a \xor (b \xor c)$

3. $0$ を中立元としてもつ。
   $a \xor 0 = a$

4. 自身を逆元としてもつ。
   $a \xor a = 0$

1. 可換である。
   $a + b = b + a$

2. 結合律を満たす。
   $(a + b) + c = a + (b + c)$

3. $0$ を中立元としてもつ。
   $a + 0 = a$

4. 反数を逆元としてもつ。
   $a + -a = 0$

1. 可換である。
   $a \times b = b \times a$

2. 結合律を満たす。
   $(a \times b) \times c = a \times (b \times c)$

3. $1$ を中立元としてもつ。
   $a \times 1 = a$

4. 逆数を逆元としてもつ。
   $a \times \frac{1}{a} = 1$

どうでしょうか? 特に注目したいのは 1 と 2 のペア, そして 4 です。

1 と 2 を両方満たしているため, XOR はどこから計算してもよいことがわかります。 たとえば, $a \xor b \xor c \xor d \xor e$ を $e \xor b \xor c \xor a \xor d$ のようにしても問題ありません。 これは同じく可換で結合律を満たす加法や乗法と同様です。

輪をかけて特徴的なのは 4 です。 加法には減法, 乗法には除法という相方がいるのですが, XOR の場合はひとりで完全体って感じです。 つよそう。

ちなみに, これら 4 個の性質をもって “アーベル群” と言います。 加法, 乗法, XOR はどれもアーベル群を成します。

ほかに特徴的な性質として,

• 符号の性質は乗法に似る。 つまり, $\text{正} \xor \text{正} = \text{正}$, $\text{正} \xor \text{負} = \text{負}$, $\text{負} \xor \text{正} = \text{負}$, $\text{負} \xor \text{負} = \text{正}$ となる。
• 非負な $a, b$ について, $a \xor b \le a + b$ がつねに成り立つ。

というものがあります。

競プロの XOR 関連の問題

これらの性質をもとに解ける競技プログラミングの問題をふたつ紹介いたします。 どちらもごくごく最近の出題で, アルゴリズム的な知識がほとんどなくても, 上記性質を知っていればあとはほんの少しの発想力だけで解ける問題です。

yukicoder contest 253 B - XOR の XOR

問題ページはこちら。

要素数 $N$ の非負整数列 $A$ があります。 $A$ の $i\ (1 \le i \le N)$ 番目の要素は $A_i$ です。

茶碗蒸しくんは, 次の操作を行います。

• $A$ を自由に並び替える。
• $B_j = A_j \xor A_{j + 1}\ (1 \le j \le N - 1)$ である非負整数列 $B$ を作る。
• $X = B_1 \xor B_2 \xor B_3 \xor \cdots \xor B_{N - 1}$ を求める。

$X$ の最大値を求めてください。

• $2 \le N \le 2 \times 10^3$
• $0 \le A_i \le 10^9$
• $N, A_i$ は整数

解答

問題文の操作を愚直に実装しようとすると, $A$ の並べ替えのパターン数は $N!$ となってしまいます。 最悪の場合 $3.3 \times 10^{5735}$ 以上になります。 かの無量大数でも $10^{68}$ (諸説あり) なのでなんかもう無理です。 一般的に $10^9$ を超える処理を行おうとするとジャッジくんがブチギレて TLE 砲でプログラムを爆破してくるので $\mathcal{O}(N!)$ のオーダーとなるこのナイーブな全探索では間に合わないことがわかります。

ここはとりあえずなんらかの方法で $A$ を並び替えたところから話を始めましょう。 そのときの $B$ は

\{B_j\}_j = (A_1 \xor A_2, A_2 \xor A_3, \ldots , A_{N - 1} \xor A_N)

であることがわかると思います。 さらに $X$ を考えると,

X = (A_1 \xor A_2) \xor (A_2 \xor A_3) \xor \cdots \xor (A_{N - 1} \xor A_N)

となります。 ここで, XOR はどこからでも計算していいのですから,

\begin{aligned}
X &= A_1 \xor (A_2 \xor A_2) \xor (A_3 \xor A_3) \xor \cdots \xor (A_{N - 1} \xor A_{N - 1}) \xor A_N \\
&= A_1 \xor 0 \xor 0 \xor \cdots \xor 0 \xor A_N \\
&= A_1 \xor A_N \\
\end{aligned}

Amazing!! 実は $X$ は $A$ のうちたった 2 項しか影響しないことがわかりました! 計算量のオーダーを $\mathcal{O}(N^2)$ に改善できましたね。 しかも XOR は可換ですから順列ではなく組み合わせでよいことがわかります。 これなら探索すべきパターンは ${}_N \mathrm{C} _2$ で済みます。 最悪でも $1999000$ ですからコンピュータなら十分間に合います。

AtCoder Beginner Contest 171 E - Red Scarf

問題ページはこちら。

猫のすぬけくんが $N$ ($\Large \text{偶数}$) 匹います。 各すぬけくんには $1, 2, \ldots N$ の番号が振られています。

各すぬけくんは首に赤いスカーフを巻いており, スカーフにはそのすぬけくんが一番好きな非負整数が $1$ つ書き込まれています。

すぬけくんたちは最近, 整数の xor (排他的論理和) と呼ばれる演算を覚えました。

早速この演算を使いたくなったすぬけくんたちは, 自分以外のすぬけくんのスカーフに書かれた整数の xor を計算することにしました。

番号 $i$ が振られたすぬけくんが計算した, 自分以外のすぬけくんのスカーフに書かれた整数の xor が $a_i$ であることが分かっています。この情報を元に, 各すぬけくんのスカーフに書かれた整数を特定してください。

• 入力はすべて整数である
• $2 \le N \le 200000$
• $N$ は$\Large \text{偶数}$
• $0 \le a_i \le 10^9$
• 与えられた情報と整合するようなスカーフ上の整数の組み合わせが存在する

解答

これみよがしに書かれた ($\Large \text{偶数}$) にはもちろん意味があります。 まあそれはさておいて, 考え方のスタートは先程と同じく, とりあえず当てはめてみることです。

各すぬけくんのスカーフに書かれた整数を $s_i$ とすると, $a_i$ はそれぞれ以下のようになることはわかると思います。

\begin{alignedat}{4}
a_1 &= & & & s_2 &\xor & s_3 &\xor \cdots \xor s_{N - 1} \xor s_N \\
a_2 &= & s_1 & & &\xor & s_3 &\xor \cdots \xor s_{N - 1} \xor s_N \\
\vdots \\
a_N &= & s_1 &\xor & s_2 &\xor & s_3 &\xor \cdots \xor s_{N - 1}
\end{alignedat}

ここで $x \xor x = 0$ を利用して穴埋めをしてみます。 以下のように書き換えても値が変わらないことはおわかりでしょうか。

\begin{aligned}
a_1 &= {\color{blue}s_1} \xor s_2 \xor s_3 \xor \cdots \xor s_{N - 1} \xor s_N \xor {\color{blue}s_1} \\
a_2 &= s_1 \xor {\color{blue}s_2} \xor s_3 \xor \cdots \xor s_{N - 1} \xor s_N \xor {\color{blue}s_2} \\
\vdots \\
a_N &= s_1 \xor s_2 \xor s_3 \xor \cdots \xor s_{N - 1} \xor {\color{blue}s_N} \xor {\color{blue}s_N} \\
\end{aligned}

ここで, $a_1 \xor a_2 \xor \cdots \xor a_N$ を考えてみましょう。すると, $x \xor x = 0$ かつ $N$ は偶数なのですから縦の軸は右端以外すべて消えてしまうことがわかります。 よって, 以下の恒等式が成り立ちます。

a_1 \xor a_2 \xor \cdots \xor a_N = s_1 \xor s_2 \xor \cdots \xor s_N

ここまでくればしめたものです。 たとえば, 右辺から任意の項 $s_n$ をピックアップしたとします。 すると残りの項は当然 $a_n$ ですから, あとは移項すればよいだけです。 XOR は一人で完全体なので移項しても変化しません。

\begin{alignedat}{2}
a_1 \xor a_2 \xor \cdots \xor a_N & & &= s_n \xor a_n \\
a_1 \xor a_2 \xor \cdots \xor a_N &\xor a_n & &= s_n \\
\end{alignedat}

Amazing!! 右辺に求めるべき値が, 左辺に入力から得られる値のみが出揃いました! これにて解決です。

まとめ

XOR には興味深い性質が多くあります。 これらへの理解を深めることで友だちが増え私生活が上手くいくようになりおまけに彼女も出来

出来ねえよバカ!