ARC173 E - Rearrange and Adjacent XORが超面白い - 獅子座じゃない人のブログ

まえがき

こんにちは、ARC173で水落ちした獅子座じゃない人です。
ARC173のE問題が単純な問題設定で一見単純な答えでありつつも、とても非自明な場合分けが必要であると感じました。
また、ARC-Eだけあって解説もとても行間が広く、行間を埋めたり別のアプローチをとって証明を試みたところ、さらに面白く感じたのでまとめます。

問題

atcoder.jp
元の問題文で理解できる問題設定だと思いますが、一応書いておきます。
長さ $N(\geq 2)$ の非負整数列 $A=(A_1,A_2,\ldots,A_N)$ が入力として与えられます。
非負整数の二項演算で、二進表記の各桁についてXORをとるものを、ビット単位XOR演算 $\oplus$ と定義しておきます。

$A$ を好きなように並び替えたものを新たな $A$ とする。
現在の $A$ の長さを $n$ として、 $(A_1\oplus A_2,A_2\oplus A_3,\ldots,A_{n-1}\oplus A_n)$ という長さ $n-1$ の数列を新たな $A$ とする。

という操作を $(N-1)$ 回繰り返した後、 $A$ は長さ $1$ の整数列になっています。
その唯一の要素を $X$ としたとき、 $X$ としてありえる非負整数の最大値を出力する問題となります。

この問題は、 $X$ としてありえる非負整数の条件を考察し、条件を満たす非負整数の最大値を求めることで解くことができます。
そして、 $X$ としてありえる非負整数の条件がとても非自明で面白いと感じました。

操作の性質

操作の前半は、 $A$ の長さを $n$ 、ある ${1,2,\ldots,n}$ の置換を $P$ として、 $A\leftarrow(A_{P_1},A_{P_2},\ldots,A_{P_n})$ という変換を行うと考えることができます。
ここで、 $P$ が等しい操作を同じ操作であると定義します。
また、長さがともに $n$ である非負整数列 $A$ と $B$ について、 $A\boldsymbol{\oplus}B=(A_1\oplus B_1,A_2\oplus B_2,\ldots,A_n\oplus B_n)$ という演算を定義しておきます。

長さが $n$ の $A$ と $B$ 、 $C=A\boldsymbol{\oplus}B$ に同じ操作を行うことを考えます。
まず、操作の前半では、 $A$ は $(A_{P_1},A_{P_2},\ldots,A_{P_n})$ 、 $B$ は $(B_{P_1},B_{P_2},\ldots,B_{P_n})$ 、そして $C$ は $(A_{P_1}\oplus B_{P_1},A_{P_2}\oplus B_{P_2},\ldots,A_{P_n}\oplus B_{P_n})$ に変換されます。
したがって、 $C=A\boldsymbol{\oplus}B$ という関係は保たれます。

改めて添字をおき直し、操作の後半について考えます。
操作の後半では、 $A$ は $(A_1\oplus A_2,A_2\oplus A_3,\ldots,A_{n-1}\oplus A_n)$ 、 $B$ は $(B_1\oplus B_2,B_2\oplus B_3,\ldots,B_{n-1}\oplus B_n)$ 、そして $C$ は $( (A_1\oplus B_1)\oplus (A_2\oplus B_2),(A_2\oplus B_2)\oplus (A_3\oplus B_3),\ldots,(A_{n-1}\oplus B_{n-1})\oplus (A_n\oplus B_n) )$ に変換されます。
$\oplus$ の交換法則より、 $C=A\boldsymbol{\oplus}B$ という関係は保たれます。

以上より、 $A$ 、 $B$ と同じ操作を $A\boldsymbol{\oplus}B$ に行った結果は、新たな $A$ 、 $B$ についての $A\boldsymbol{\oplus}B$ になることがわかりました。

また、 $\oplus$ の性質より、列の要素は $0$ か $1$ であるとしてしまって問題ありません。
二進の各桁について新たな列を作り、それぞれに同じ操作を行ったと考えることができます。

条件の考察

$0$ か $1$ からなる長さ $N$ の列について、第 $i$ 項のみが $1$ で他の項は全て $0$ であるものを $e_i\ (1\leq i\leq N)$ とします。
操作の性質から、各 $e_i$ に同じ $(N-1)$ 回の操作を行って得られる $X$ の組み合わせについて考えればよいです。

結論を先に述べます。
ある $(N-1)$ 回の操作によって $k$ 個の $e_i$ が $X=1$ となった場合、 $k$ 個の $e_i$ が $X=1$ となる全ての組み合わせについて、それを得る $(N-1)$ 回の操作が存在します。
したがって、 $X=1$ となる $e_i$ の個数 $k$ についてのみ注目すればよいです。
$N=2$ または $N\not\equiv 2\ (\!\!\!\!\!\mod 4)$ の場合、 $k$ は $2$ 以上 $N$ 以下の全ての偶数をとります。
$N\neq 2$ かつ $N\equiv 2\ (\!\!\!\!\!\mod 4)$ の場合、 $k$ は $2$ 以上 $N-2$ 以下の全ての偶数をとります。

ある $(N-1)$ 回の操作によって $k$ 個の $e_i$ が $X=1$ となった場合、 $k$ 個の $e_i$ が $X=1$ となる全ての組み合わせについて、それを得る $(N-1)$ 回の操作が存在することを、まず証明します。
一回目の操作で並び替えを行うことは、 $e_i$ の列を置換したのと同じになります。
したがって、一回目の操作で並び替えを行わなかった場合と $X=1$ となる $e_i$ の個数は同じになり、一回目の操作で並び替えを適当に行うことで $k$ 個の $e_i$ が $X=1$ となる任意の組み合わせに対応する操作を考えることができます。

次に、ありうる $k$ が上のようになることを数学的帰納法で証明します。
まず、 $N=2$ について、 $e_1=(1,0)$ に操作を行うと $1$ が得られ、 $e_2=(0,1)$ に操作を行うと $1$ が得られることから示されます。

次に、 $N=n-1(\geq 2)$ で成り立つことを仮定し、 $N=n$ について考えます。
一回目の操作で並び替えを行わないとします。
すると、 $e_i$ から得られる $X$ は $({e_i}_1,{e_i}_2,\ldots,{e_i}_{N-1})$ と $({e_i}_2,{e_i}_3,\ldots,{e_i}_N)$ に同じ $(N-2)$ 回の操作を行って得られる $X$ （それぞれ $X_1,X_2$ とします）についての $X_1\oplus X_2$ になります。

第 $i$ 項のみが $1$ で他の項は全て $0$ である長さ $N-1$ の列に、ある $(N-2)$ 回の操作を行って得られる $X$ を $x_i\ (1\leq i\leq N-1)$ とします。以降、この記法を複数用いる場合、全て同じ操作であることを仮定します。
$e_1$ から得られる $X$ は $x_1$ 、 $e_i\ (2\leq i\lt N)$ から得られる $X$ は $x_{i-1}\oplus x_i$ 、 $e_N$ から得られる $X$ は $x_{N-1}$ となります。
これをもとに、 $X=1$ となる $e_i$ の個数としてありえるものを考えることになります。

ここで、先に $X=1$ となる $e_i$ の個数の偶奇について先に考えておきます。
和の偶奇のみを求めるのはまさしくXORそのものです。
$x_1\oplus(x_1\oplus x_2)\oplus(x_2\oplus x_3)\oplus\cdots\oplus(x_{N-2}\oplus x_{N-1})\oplus x_{N-1}=0$ より、 $X=1$ となる $e_i$ の個数は偶数であることがわかります。

$1.$ $N\equiv 1\ (\!\!\!\!\!\mod 4)$ または $N=3$ の場合
$x_i=1$ となる個数は $2,4,\ldots,N-1$ が考えられます。
したがって、 $x_{N-1}$ 以外の $x_i$ は自由に決めることができます。ただし、全ての $x_i\ (i\lt N-1)$ が $0$ である場合のみ作れません。
つまり、 $e_{N-1},e_N$ 以外から得られる $(N-2)$ 個の $X$ は自由に決めることができます。ただし、 $e_i\ (i\lt N-1)$ までから得られる全ての $X$ が $0$ である場合のみ作れません。
また、 $X=1$ となる $e_{N-1},e_N$ 以外の $e_i$ の個数が奇数であった場合、必ず $e_{N-1},e_N$ から得られる $X$ の片方のみが $1$ となります。
よって、 $X=1$ となる $e_i$ の個数として、 $2$ から $N-1$ までの全ての偶数がありえることがいえました。
また、 $X=1$ となる $e_i$ の個数を $0$ にすることはできないこともいえるため、 $X=1$ となる $e_i$ の個数としてありえるのは、 $2$ 以上 $N$ 以下の全ての偶数であることがわかりました。

$2.$ $N\equiv 3\ (\!\!\!\!\!\mod 4)$ かつ $N\gt 3$ の場合
$x_i=1$ となる個数は $2,4,\ldots,N-3$ が考えられます。
全ての $x_i$ を $1$ にできないことのみ、 $1.$ の場合と異なります。
しかし、全ての $x_i$ が $1$ である場合の $X=1$ となる $e_i$ の個数は $(N+1)/2$ 個であり、別の $x_i$ の組み合わせによって達成できます。
よって、 $1.$ と同様の議論により、 $X=1$ となる $e_i$ の個数としてありえるのは、 $2$ 以上 $N$ 以下の全ての偶数であることがわかりました。

$3.$ $N\equiv 0\ (\!\!\!\!\!\mod 4)$ の場合
$x_i=1$ となる個数は $2,4,\ldots,N-2$ が考えられます。
したがって、 $x_{N-1}$ 以外の $x_i$ は自由に決めることができます。
つまり、 $e_{N-1},e_N$ 以外から得られる $(N-2)$ 個の $X$ は自由に決めることができます。
ほとんどの偶数については $1.$ と同様の議論により、達成できることがいえます。しかし、 $0$ と $N$ については別に考える必要があります。
$X=1$ となる $e_i$ の個数を $0$ にするには、 $x_i=1$ となる個数が $0$ である必要があり、これは無理です。
一方、 $X=1$ となる $e_i$ の個数を $1$ にするには、 $x_i=1$ となる個数が $N/2$ である必要があります。 $N/2$ は偶数であり、問題ありません。
よって、 $X=1$ となる $e_i$ の個数としてありえるのは、 $2$ 以上 $N$ 以下の全ての偶数であることがわかりました。

$4.$ $N\equiv 2\ (\!\!\!\!\!\mod 4)$ かつ $N\gt 2$ の場合
$x_i=1$ となる個数は $2,4,\ldots,N-2$ が考えられます。
$3.$ と同様の議論をすることができますが、 $3.$ の場合と異なり、 $N/2$ は奇数となります。
よって、 $X=1$ となる $e_i$ の個数を $N$ にすることはできないことがいえ、 $X=1$ となる $e_i$ の個数としてありえるのは、 $2$ 以上 $N-2$ 以下の全ての偶数であることがわかりました。

以上より、ありうる $k$ が上のようになることがいえました。
この条件を、一般の $A$ に応用します。

$A_i$ の二進での $d$ 桁目を $A_i^{(d)}$ とします。
元の非負整数列 $A$ の二進の各桁について新たな列を作り、それぞれに同じ操作を行ったと考えます。
すると、各列は $e_i$ を使って、 $\pmb{\bigoplus}_{\{i\ |\ A_i^{(d)}=1\}} e_i$ と表せます。
したがって、 $e_i$ からある $(N-1)$ 回の操作を行って得られる $X$ を $x_i$ として、各列から得られる $X$ は $\bigoplus_{\{i\ |\ A_i^{(d)}=1\}} x_i$ と表せます。
XORの単位元が $0$ であり、 $A_i^{(d)}$ も $x_i$ もともに $0$ か $1$ をとることから、 $\bigoplus_{\{i\ |\ A_i^{(d)}=1\}} x_i=\bigoplus_{\{i\ |\ x_i=1\}} A_i^{(d)}$ と書き換えられます。
各桁に対してのこの結果を合わせると、 $A$ から得られる $X$ としてありえるのは $\bigoplus_{\{i\ |\ x_i=1\}} A_i$ の形であることがわかりました。

結局、長さ $N$ の $A$ から得られる $X$ として、 $A$ から好きに $k$ 個とった総ビット単位XOR演算の結果が全てありえることがわかりました。
ここで、 $N=2$ または $N\not\equiv 2\ (\!\!\!\!\!\mod 4)$ の場合、 $k$ は $2$ 以上 $N$ 以下の全ての偶数をとり、 $N\neq 2$ かつ $N\equiv 2\ (\!\!\!\!\!\mod 4)$ の場合、 $k$ は $2$ 以上 $N-2$ 以下の全ての偶数をとります。

条件を踏まえた解法

まず、 $A_1\oplus A_2,A_1\oplus A_3,\ldots,A_1\oplus A_N$ を考えると、それから一部をとっての総ビット単位XOR演算は必ず $A$ から偶数個とった総ビット単位XOR演算と同じになります。
$A_1\oplus A_1=0$ より、 $A_1\oplus A_2,A_1\oplus A_3,\ldots,A_1\oplus A_N$ から奇数個とっての総ビット単位XOR演算は $A_1$ を含んで偶数個とった総ビット単位XOR演算となります。
そして、 $A_1\oplus A_2,A_1\oplus A_3,\ldots,A_1\oplus A_N$ から偶数個とっての総ビット単位XOR演算は $A_1$ を含まず偶数個とった総ビット単位XOR演算となります。

したがって、この問題は $A_1\oplus A_2,A_1\oplus A_3,\ldots,A_1\oplus A_N$ の部分集合の総ビット単位XOR演算の最大値を求める問題に帰着されます。
この問題は有名問題であり、たとえばこのような方法で時間 $\Theta(Nd)$ （ただし $d$ は二進での桁数）で求めることができます。
www.geeksforgeeks.org

$A$ から一つもとらない場合は $0$ なので気にする必要はないですが、 $N\neq 2$ かつ $N\equiv 2\ (\!\!\!\!\!\mod 4)$ の場合は $A$ から全て選んでしまう場合を考慮する必要があります。
$A_i$ を使わない場合を全探索すればよく、この場合でも時間 $\Theta(N^2 d)$ で求められます。
公式解説では、noshi基底を用いて線形独立でない場合やそもそも $A$ から全て選んで最大値にならない場合を先に省いていますが、それをしなくても最悪計算量のオーダーは変わりません。（もちろん最良計算量のオーダーは変わります。）