\(A_i < 2^L\) なるように \(L\) をとる．

以下 \(x_i\) が入力だとして Bob のことだけを考える． 問題は次のように言い換えられる．

\(x\) に \(2^p-1\) の形の非負整数を好きな個数追加し，新しい集合 \(v\) を作る． \(v_i\) を適切に並び替え，その累積 XOR を \(y'_i\) とする． ここで，\(y'_i\) が広義単調増加である必要がある． \(y'_i\) の末尾の項がスコア．

言い換えの正当性は次のようにわかる． まず，\(y'\) から \(y\) を得るには，\(x_i\) 由来の項の前後の \(y'_i\) だけ取り出して \(y\) とすればよい． 逆に \(y\) から \(y'\) を得るには，\(y_{2i},y_{2i+1}\) の間を \(y_{2i},y_{2i}+1,\cdots,y_{2i+1}\) と分割すればよい．

言い換え後の問題の解き方． まず \(v\) が固定されたときに，条件を満たす \(y'\) が作れるか判定する．（\(y'\) の末尾の項は \(v\) の並び替えに依らないので判定問題が重要）

すべての非負整数 \(p=0,1,\cdots\) に対し，\(v_i/2^p\) (の整数部分) を考えたときに prefix XOR を広義単調増加にできればよい． \(v_i/2^{p+1}\) について条件を満たすような列が取れたとしよう． ここから \(v_i/2^p\) についての解を作ってみる． \(v_i/2^p \geq 2\) になる \(v_i\) については，\(v_i/2^{p+1}\) に対する解と同じ順番で並べれば \(v_i/2^p\) に関しても条件を満たしている． あとはここに \(v_i/2^p=1\) となる \(v_i\) をうまく挿入して prefix XOR を広義単調増加のままにしたい． これが可能かどうかの判定は簡単． \(v_i/2^p \geq 2\) かつ \(v_i/2^p\) が奇数であるような \(v_i\) の個数を \(a\), \(v_i/2^p =1\) であるような \(v_i\) の個数を \(b\) とおくと，\(b \leq a+1\) かどうかを見ればよい． \(v_i/2^p\) の prefix XOR が偶数になったら毎回 \(v_i/2^p=1\) なる \(v_i\) を追加する，という操作を考えれば，\(b \leq a+1\) ならば条件を満たす列が構成可能であるし，逆に \(b>a+1\) ならばどうやっても構成不可能になる．

これで \(v\) が固定された場合の問題は解けた． あとは \(v\) を色々動かして，判定問題が真になる範囲で総 XOR (\(d\)とおく) を最小化する問題を考える．

\(d\) を一つ固定した際の判定を考える． 上の bit から条件を合わせていくことを考える． \(d\) の下から \(p\) bit 目の値を \(d_p\) とおく．

まず \(v=x\) としておく． \(p=60,59,\cdots\) に対し，\(p\) bit 目について注目して，\(v\) に値を追加していく． \(x_i/2^p \geq 2\) かつ \(x_i/2^p\) が奇数であるような \(x_i\) の個数を \(a_p\), \(x_i/2^p =1\) であるような \(x_i\) の個数を \(b_p\)，今までに追加すると決めた数の個数を \(c_p\) とする． 最上位 bit が \(p\) bit 目になる数 (\(=2^{p+1}-1\)) をいくつ追加するか考える． できるだけ多く追加したほうが後々嬉しいことと，XOR が \(d_p\) に一致することを考えると，\(a_p+c_p-b_p+d_p\) 個追加するべきだとわかる． この個数が負であれば，この \(d\) は達成不可能であると判定できる．

\(a_p+c_p-b_p+d_p \geq 0\) という形の不等式は，結局 \(p < L\) の範囲だけで重要になる．この \(L\) 個の不等式を更に整理する． \(a_p,b_p\) は入力の \(x_i\) から直ちに計算できる値である． また，\(c_p+(a_p+c_p-b_p+d_p)=c_{p-1}\) という関係式を用いると，\(c_p\) はすべて \(a_j,b_j,d_j\) の和で書けることがわかる． 結局，各不等式は，\(d_{p}+d_{p+1}+2d_{p+2}+4d_{p+3}+\cdots \geq e_p\) (\(e_p\) は入力の \(x_i\) から計算できる値) という形になる． これを更に変形すると，\(d \geq 2^p(2e_p-1)\) とできる． 結局，\(2^p(2e_p-1)\) の max を求めるとそれが \(d\) になる．

Bob についてわかったので Alice 側の戦略について考える．

\(e_p\) は \(x\) から計算するわけだが，各 \(x_i\) ごとに寄与が独立であるとわかる． つまり，\(e_{i,p}\) という値が \(x_i\) から計算でき，\(e_p=\sum_{1 \leq i \leq k} e_{i,p}\) という形になる．

よって Alice 側の戦略としては，各 \(A_i\) に対応する \(e_{i,j}\) をすべて求めたあと，各 \(p\) について \(e_{i,p}\) を大きい順に並べ，それを先頭から \(k\) 個取ることを試せばよい．

計算量は \(O(NL\log(N))\) になる．

実装例