D - XOR Game Editorial by maroonrk_admin
スコアが \(v\) 以下になるかどうかを考えます.
もし,\(A_i\) を \(N\) 個のペアに分け,それぞれのペアの XOR の値をすべて \(v\) 以下にすることが可能ならば,Bob は常にペア分けに従って行動することで,スコアを \(v\) 以下にできます.
逆に,上記のペア分けが存在しない場合,必ずスコアは \(v+1\) 以上です.これは, \(v\) 以下だとすると明らかに矛盾するためです.
よってこの問題は,\(A_i\) をマッチングさせ,ペアの XOR の値を最小化する問題になります.
\(L=30\) とします. 答えの下から \(L\) bit 目が \(1\) になるかどうかをまず考えます. もし,下から \(L\) bit 目が \(0\) になる数と \(1\) になる数がそれぞれ偶数個なら,\(0/1\) で数を分類し,それぞれ同じ問題を \(L:=L-1\) として解けばよいです. そうでない場合,\(L\) bit 目が \(0\) の数と \(1\) の数のペアを一つは必ず作らないといけません. 逆に,一つ作ってしまえば,残りは \(0\) 同士,\(1\) 同士でマッチングできます.
よって,この問題は,数の集合 \(X\) と \(Y\) があり,\(X,Y\) から \(1\) つずつ要素を選んで XOR を最小化する,という問題に帰着されます. これは,Trie 木を作ることで解くことができます.
計算量は全体で \(O(NL)\) です.
posted:
last update: