Pythonでサイズkの全セグメントのXORをゼロにするための最小変更数を求めるプログラム

配列 nums と整数 k が与えられます。セグメント [left, right](left ≤ right)のXORとは、インデックス left から right まで(両端を含む)のすべての要素をXOR(排他的論理和)した値のことです。

この問題では、サイズ k のすべてのセグメントのXORが 0 となるように配列を書き換えるとき、変更が必要な要素数の最小値を求めます。

たとえば、入力が nums = [3,4,5,2,1,7,3,4,7]、k = 3 の場合、答えは 3 になります。インデックス 2・3・4 の要素を書き換えて [3,4,7,3,4,7,3,4,7] とすれば、どの長さ3の区間を取ってもXORが 0 になるからです。

解法のポイント

長さ k のスライディングウィンドウを1つずらすことを考えると、新しいウィンドウのXORは、直前のウィンドウから先頭の要素 nums[i] を外し、代わりに末尾へ nums[i+k] を加えたものになります。すべてのウィンドウのXORが 0 でなければならない以上、必ず nums[i] = nums[i+k] が成り立っている必要があります。

つまり、「インデックスを k で割った余りが等しい位置の要素は、すべて同じ値に揃える」ことになります。すると問題は「余りごとのグループごとに代表値を選び、そのXOR全体が 0 になるようにしながら変更数を最小化する」という最適化問題に帰着でき、動的計画法(DP)で解くことができます。

アルゴリズムの手順

1. LIMIT := 1024(取り得る値の範囲)とする。
2. temp := サイズ LIMIT × k の表を作り、0 で初期化する。
3. nums の各インデックス i と各値 x について、temp[i mod k][x] を 1 増やして、余りごとの出現回数を集計する。
4. dp := 長さ LIMIT の配列を −2000 で初期化し、dp[0] := 0 とする。dp[j] は「処理済みグループの代表値のXORが j のとき、変更せずに残せる要素数の最大値」を表す。
5. temp の各行(各グループ)について以下を実行する。
   • maxprev := dp の最大値。
   • new_dp := 長さ LIMIT の配列を maxprev で初期化する(現在のグループの要素をすべて変更する選択肢に相当)。
   • 行の中の各値 i と出現回数 cnt について(cnt > 0 のとき)、dp の各状態 j・prev に対して new_dp[i XOR j] := max(new_dp[i XOR j], prev + cnt) と更新する。
   • dp := new_dp で置き換える。
6. len(nums) − dp[0] を返す。これがXORを 0 に揃えるための最小変更数となる。

Pythonでの実装例

def solve(nums, k):
    LIMIT = 2 ** 10
    # インデックスをkで割った余りごとに、各値の出現回数を集計
    temp = [[0] * LIMIT for _ in range(k)]
    for i, x in enumerate(nums):
        temp[i % k][x] += 1

    # dp[j]: 処理済みグループのXORがjのとき、変更せず残せる要素数の最大値
    dp = [-2000] * LIMIT
    dp[0] = 0
    for row in temp:
        maxprev = max(dp)
        new_dp = [maxprev] * LIMIT
        for i, cnt in enumerate(row):
            if cnt > 0:
                for j, prev in enumerate(dp):
                    new_dp[i ^ j] = max(new_dp[i ^ j], prev + cnt)
        dp = new_dp
    return len(nums) - dp[0]

nums = [3, 4, 5, 2, 1, 7, 3, 4, 7]
k = 3
print(solve(nums, k))

入力

[3,4,5,2,1,7,3,4,7], 3

出力

3

動作の確認

サンプルでは、インデックスを 3 で割った余りごとに次の3つのグループに分かれます。

• グループ0(インデックス 0, 3, 6):値は 3, 2, 3
• グループ1(インデックス 1, 4, 7):値は 4, 1, 4
• グループ2(インデックス 2, 5, 8):値は 5, 7, 7

それぞれ 3・4・7 を代表値として選ぶと、3 XOR 4 XOR 7 = 0 となり条件を満たします。このとき各グループで1個ずつ、合計3個の要素を書き換えればよく、これが最小変更数です。

計算量

値の種類を V(ここでは 1024)、グループ数を k とすると、各グループの更新に最大 O(V²) かかるため、時間計算量は O(n + k·V²)、空間計算量は O(k·V) となります。V が定数上限に収まる前提であれば、n や k が適度な規模なら十分実用的な速度で動作します。