AtCoder Beginner Contest 141 F - Xor Sum 3

お題箱より。

F - Xor Sum 3

線形代数を用いた解法の正当性について理解したい…というリクエストだったので、そこを重点的に書きます。

前段の考察

$2^{d}$ を表すビット桁を $d$ 桁目と表記することにします。一番下が0桁目です。

各ビット桁ごとに、 $A_{1}, ..., A_{N}$ のうち $d$ 桁目が立っている要素の個数を $n_{d}$ と表記します。

$n_{d}$ が奇数である場合、2つのグループにどう分けても $d$ 桁目のビットは最終的な答えに $2^{d}$ 貢献します。

一方偶数である場合、それが奇数個ずつ分かれると答えに $2^{d}\times 2$ 足され、偶数個ずつ分かれると答えには何も足されません。

よって前段の考察は以下のようになります。

$n_{d}$ が奇数である桁について $2^{d}$ を合計したものを求めておき、これを $S_{1}$ とする。 $A_{1}, ..., A_{N}$ からこれらの桁のビットを消去する。
$n_{d}$ が偶数である桁だけが残った $A_{1}, ..., A_{N}$ から、いくつかの要素を選んだもののXOR和の最大値を求める。これを $S_{2}$ とする。
$S_{1} + 2S_{2}$ が答えである。

掃き出し法による解法のアウトライン

このある与えられた整数たちから、いくつかの要素を選んだもののXOR和の最大値を求めるという問題を解くのに有効なのが線形代数のテクニックです。特に「掃き出し法」と呼ばれる方法によってこの問題を解きます。

Gauss-Jordan の掃き出し法と、F2 上の連立一次方程式の解の個数 - けんちょんの競プロ精進記録

上記リンク先の記事に詳しくまとまっていますが、解法のアウトラインとしては

与えられた整数たちを、各整数を行、各ビット桁を列とする行列と見なす。
この行列に対して「行基本変形」を行い、「行標準形」に変換する。
「行標準形」となった行列に対して上位桁から貪欲に値を決めていく。

というステップになります。

なぜこの方法が正しいのかという理由付けは、

行基本変形を施しても問題の答えが不変であること。
行標準形となった行列に対して、上位桁から貪欲に値を決めていくことで必ず最大値が求められること。

の2点に集約されるかと思います。それぞれ見ていきましょう。

行基本変形によって答えが変わらないことを示す

行基本変形と呼ばれるものは、3種類の操作を含んでいます。

ある行とある行を入れ替える。
ある行を異なる行に足し合わせる。
ある行を0でない定数倍する。

今回考えるのは $F_{2}$ と呼ばれる、各成分の値が $\lbrace 0, 1\rbrace$ しかなく足し算としてXOR演算を採用した世界での線形代数です。そのため「0でない定数倍」というのは、0でない定数が1しかないため実質的に意味ありません。

「ある行とある行を入れ替える」操作は元の問題でいう要素同士のインデックス交換に相当し、これは当然ながら答えに影響を与えません。少し考える必要があるのは「ある行を異なる行に足し合わせる」という操作で、これは元の問題で「ある要素を異なる要素にXORで足す」という操作に相当します。これで答えが変わらないことを示します。

説明を具体的にするため $N=3$ とします。 $A_{1}, A_{2}, A_{3}$ のうち0個以上の任意の要素を選ぶ選び方は $2^{3} = 8$ 通りあります。それぞれの選び方に対してXOR和を計算した結果を集めた多重集合を $S$ と書くことにすると、これは以下のようになります。

$S = \lbrace 0, A_{1}, A_{2}, A_{3}, A_{1}\oplus A_{2}, A_{2}\oplus A_{3}, A_{3}\oplus A_{1}, A_{1}\oplus A_{2}\oplus A_{3}\rbrace$

これに対して、「ある要素を異なる要素にXORで足す」という操作をした数列 $A_{1}, A_{2}, A_{3}\oplus A_{1}$ を考えます。これに対して同様に、8通りの選び方についてXOR和を計算した結果を集めると、これは多重集合として $S$ と同じになります。

$S^{\prime} = \lbrace 0, A_{1}, A_{2}, A_{3}\oplus A_{1}, A_{1}\oplus A_{2}, A_{2}\oplus A_{3}\oplus A_{1}, A_{3}, A_{2}\oplus A_{3}\rbrace$

具体的には元々 $A_{3}$ を含んでいたような選び方全てに対して、「 $A_{1}$ を含むかどうか」が反転します。全ての選び方に対して「 $A_{1}$ を含むかどうか」だけが異なる別の選び方が存在するので、それらが反転するだけで集合としては同じになります。

これは要素数がいくつであっても同様に成り立ちます。XOR和としてあり得る値の集合が同じということは、その最大値も同じなので、この操作で答えが変わらないことが示せます。

行標準形となった行列に対して、上位桁から貪欲に値を決めていけることを示す

まず、 $F_{2}$ における行標準形の概形を示します。グレーのところは全て0です。図に併記している通り、左側の列のほうが上位桁とします（実際はもっと桁数が多いです）。

f:id:betrue12:20191122004133p:plain

赤で書いている1が「ピボット」と呼ばれるもので、行標準形では各行の0でない先頭要素が必ずピボットになります。またピボットを含む列は、ピボット以外全て0になります（そのように変形します）。

これを上位桁から順番に見ていき、XOR和を最大にする選び方を決めます。

まず見ている桁にピボットがある場合。この場合、この桁のビットを立てる唯一の方法は、このピボットが存在する行を採用することです。またこの行を採用することで上位ビットには影響を与えないので、必ずこの行を採用することにして良いです。

f:id:betrue12:20191122004447p:plain

次に、見ている桁にピボットがない場合。今まで採用した行によるこの桁のXOR和は0か1のどちらかになっています。この値を変えようと思うと、図中の「?」に相当するどこかの行の採用/不採用を変える必要があります。しかしこれらの行は必ず上位桁でピボットのビットを立てているので、必ず既に採用されていて、これを不採用にするとその上位ビットを消してしまうことになります。これは必ず損をします。

f:id:betrue12:20191122004700p:plain

つまり結局、行標準形にしてしまった後にはピボットを含む行（つまり、0でない全ての行）を全て採用することでXOR和が最大化されることになります。

以上がこの解法の正当性の説明になります。例えばこれが最大値ではなく「ぴったりある値 $X$ に一致させられるか判定せよ」という問題であっても、各ピボットの桁によって採用/不採用が一意に制約され、他の桁が一致するかどうかで判定ができます。ある与えられた整数たちから、いくつかの要素を選んだもののXOR和について何かするという問題においては、線形代数のテクニックが有効に使えることが多いです。