Pythonで指定範囲内のXORとなるペアを数えるアルゴリズムと実装例

問題の概要

配列 nums と2つの整数値 l、r が与えられたとき、「良いペア(nice pair)」の総数を求めることを考えます。ここで良いペアとは、インデックスの組 (i, j) が次の条件を満たすものを指します。

• 0 <= i < j < 配列の長さ
• l <= (nums[i] XOR nums[j]) <= r

入力例と出力例

たとえば、nums = [4,1,7,2]、l = 2、r = 6 が入力として与えられた場合、出力は 6 になります。これは、以下の6組が良いペアに該当するためです。

• (0, 1): 4 XOR 1 = 5
• (1, 2): 1 XOR 7 = 6
• (1, 3): 1 XOR 2 = 3
• (0, 3): 4 XOR 2 = 6
• (0, 2): 4 XOR 7 = 3
• (2, 3): 7 XOR 2 = 5

解法のアプローチ

この問題は、すべてのペアを素朴に全探索すると計算量が O(n²) となり、配列が大きい場合には非効率です。そこで、ビットごとの桁に着目した効率的な手法を用います。基本的なアイデアは「XOR の結果が x 未満になるペアの個数を求める関数」を作成し、f(r + 1) - f(l) を計算することで範囲 [l, r] 内に収まるペア数を導き出すというものです。

アルゴリズムの手順

• 関数 test(nums, x) を定義します。これは「XOR の結果が x 未満になるペアの個数」を返します。
• count を、配列内の各要素の出現頻度を保持するマップ(Counter)として初期化します。
• 結果を格納する変数 res を 0 で初期化します。
• x が 0 でない限り、以下を繰り返します。
  • x が奇数の場合、count[a] * count[(x - 1) XOR a] の総和を res に加算します(a は count のすべてのキー)。
  • count を更新します。新しいキーは a >> 1(右シフト)、値は count[a] + count[a XOR 1] となります。これにより、各要素を1ビット右にシフトし、最下位ビットを反転させた隣接要素と統合します。
  • x を 2 で割って右シフトします(x >>= 1)。
• 最後に res / 2 の商を返します。各ペアが2回カウントされるためです。
• メイン処理では test(nums, r + 1) - test(nums, l) を返します。

Pythonでの実装例

それでは、上記のアルゴリズムを実際の Python コードで確認してみましょう。

from collections import Counter

def solve(nums, l, r):
    def test(nums, x):
        count = Counter(nums)
        res = 0
        while x:
            if x & 1:
                res += sum(count[a] * count[(x - 1) ^ a] for a in count)
            count = Counter({a >> 1: count[a] + count[a ^ 1] for a in count})
            x >>= 1
        return res // 2

    return test(nums, r + 1) - test(nums, l)

nums = [4,1,7,2]
l = 2
r = 6
print(solve(nums, l, r))

入力

[4,1,7,2], 2, 6

出力

6

計算量とポイント

このアルゴリズムの時間計算量は、ビット長を b とすると O(b × n) 程度に抑えられます。全ペアを調べる O(n²) と比較して、n が大きいケースでも高速に動作するのが大きな利点です。

実装上の重要なポイントは以下の通りです。

• Counter の活用: 各段階で要素をまとめることで、同じ値を持つ要素を一括処理できます。
• ビットシフトによる段階的な判定: 上位ビットから順に比較していくことで、XOR 値がしきい値未満であるペアを効率的に数え上げます。
• 二重カウントの除去: ペア (i, j) と (j, i) が両方数えられるため、最後に 2 で割っています。

このように、XOR の性質とビット演算を組み合わせることで、範囲制約付きのペアカウント問題を効率的に解くことができます。競技プログラミングやデータ分析の場面でも応用できるテクニックなので、ぜひ理解を深めておきましょう。