https://atcoder.jp/contests/abc141/tasks/abc141_f
$N$個の非負整数が与えられる。これらの整数を2つのグループに分け、各グループの整数をすべてxorしたものをそれぞれ$A,B$とするとき、$A+B$の最大値を求めよ。
前提として $$A+B=A\;xor\;B+2(A\;and\;B)$$ であり、この問題では$A\;xor\;B$は$N$個の整数の総xorと同じなので常に一定であり、$A+B$を最大化することは$A\;and\;B$を最大化することと同じである。さらに、総xorで1になっている桁は$A\;and\;B$では必ず0になるので、これも一定である。
ここで、最初に与えられた$N$個の整数すべてに対して、総xorで1になっている桁を予めすべて0にしておくことを考える。この操作のあとでは、$N$個の整数の総xorは必ず0になっているはずであって、これらの整数をどのようにグループ分けしても必ず$A=B$となることがわかる。よって、$A\;and\;B=A=B$であり、この問題は$N$個の整数の中から任意の個数を取り出してその総xorを最大化する問題と考えることができるようになる。なお、総xorで1であるような桁は$A\;and\;B$では必ず0になる桁であるから、操作の前後で$A\;and\;B$の最大値が変化することはない。
$N$個の整数の中から任意の個数を取り出してその総xorを最大化する問題を考える。ある整数の集合について、その任意の要素を他の任意の要素にxor演算しても、その集合からいくつか選んでxorすることによって作れる整数の集合は変わらない（その操作を行う前に作れた整数が作れなくなったり、作れなかった整数が作れるようになったりはしない）。なぜなら、$a\;xor\;a=0$だからであり、例えば2つの整数のうち1つめを2つめにxorしたとき、2つめだけを使うことは操作前の集合から両方の整数を使うことに対応し、操作後の集合で両方の整数を使うことは操作前の集合から2つめだけを使うことに対応するからである。この性質を利用して、前述の問題を考える。
整数の各bitを行ベクトルとして、これを縦に$N$個並べることで行列を構成する。たとえば$\{3,6,5\}$であれば $$\left( \begin{array}{rr} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{array} \right)$$ であって、このような行列に対して掃き出し法を適用すると $$\left( \begin{array}{rr} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{array} \right)$$ のようになり、上から貪欲に1にできる桁を決めていくことができる。掃き出し法の各操作は「行をswapする」「ある行を別の行にxorする」の2つの操作からなり、これらの操作を行っても良いことは先に述べた。
掃き出し法を行った後にすべての行をxorしてできる整数は、「総xorで1になっている桁をすべて0にする操作を行った整数の集合の中から任意の個数選んでxorを取ることで作れる最大の整数」であって、$A\;and\;B$の最大値である。よってこれを2倍して、操作前の総xorを足したものが求める答えになる。
難しくて、本番中になにも方針を立てられなかった。時間はあったはずなので、せめて解法の第2段落くらいまでは考察したかった。