Pythonで各クエリの最大XORを求めるプログラムの実装方法

問題の概要

あらかじめソートされたサイズnの配列numsが与えられているとします。この配列に対して、次のクエリをn回実行することを考えます。

• 配列nums内のすべての要素とkとのXORが最大化されるような、非負の値k（k < 2^m）を求めます。このkがi番目のクエリに対する答えになります。
• 現在の配列numsから末尾の要素を1つ削除します。

そして、i番目のクエリへの答えがanswer[i]となるような配列answerを求めるのが目的です。

入力例と出力例

たとえば、入力がnums = [0,1,1,3]、m = 2の場合、出力は[0,3,2,3]になります。その理由は以下の通りです。

• nums = [0,1,1,3] のとき：0 XOR 1 XOR 1 XOR 3 XOR 0 = 3 となるため、k = 0
• nums = [0,1,1] のとき：0 XOR 1 XOR 1 XOR 3 = 3 となるため、k = 3
• nums = [0,1] のとき：0 XOR 1 XOR 2 = 3 となるため、k = 2
• nums = [0] のとき：0 XOR 3 = 3 となるため、k = 3

解法のアプローチ

この問題は、累積XOR（プレフィックスXOR）の性質を利用すると、各クエリを定数時間で処理できる効率的なアルゴリズムになります。手順は以下の通りです。

• x := 2^m - 1 として初期化します。
• i を 0 から nums のサイズ - 1 まで繰り返します。
  • nums[i] := nums[i] XOR x
  • x := nums[i]
• 配列を反転して返します。

なぜこの方法で動作するのか

XORの性質上、配列全体のXOR値をSとすると、「S XOR k」を最大化するには k = S XOR (2^m - 1) とすればよいことが分かります。これは累積XORを順番に更新していくことで、配列を一度走査するだけで求められます。ループ終了後、各要素にはその時点での累積XORに対応する答えが格納されているため、配列を反転するだけでクエリ順の答えの配列が完成します。

実装例（Python）

それでは、実際の実装を見ていきましょう。

def solve(nums, m):
   x = 2**m - 1
   for i in range(len(nums)):
      nums[i] ^= x
      x = nums[i]
   return nums[::-1]

nums = [0,1,1,3]
m = 2
print(solve(nums, m))

入力

[0,1,1,3], 2

出力

[0, 3, 2, 3]

まとめ

本記事では、配列の末尾要素を1つずつ削除しながら、残りの全要素とのXORが最大になる値kを各クエリで求める問題を扱いました。累積XORを活用することで、配列を一度走査するだけで全体を解くことができ、計算量はO(n)と非常に効率的です。ビット演算の性質を理解しておくと、この種の問題に強くなれるので、ぜひ参考にしてみてください。