【C++】2つのバイナリ配列のXORを別の配列と等しくするための最小フリップ回数

問題文

0と1のみから構成される、長さnの3つの配列が与えられます。求めたいのは、1つ目と2つ目の配列のビットをできるだけ少ない回数反転（フリップ）させて、「1つ目の配列のi番目の要素」と「2つ目の配列のi番目の要素」のXORが、「3つ目の配列のi番目の要素」と一致するようにするための最小反転回数です。

ただし、配列1については最大p個、配列2については最大q個までしかビットを反転できません。また、配列の要素を並べ替えることは許されていません。

ここでは、p = 2、q = 5 の場合を例に考えてみましょう。

arr1[] = {1, 0, 1, 1, 0, 1, 0}
arr2[] = {0, 1, 0, 1, 0, 0, 1}
arr3[] = {0, 1, 1, 0, 0, 0, 0}

• (arr1[0] ^ arr2[0]) = (1 ^ 0) = 1 となり、arr3[0]（= 0）とは一致しないため、反転が必要です。
• (arr1[1] ^ arr2[1]) = (0 ^ 1) = 1 となり、arr3[1]（= 1）と一致するため、反転は不要です。
• (arr1[2] ^ arr2[2]) = (1 ^ 0) = 1 となり、arr3[2]（= 1）と一致するため、反転は不要です。
• (arr1[3] ^ arr2[3]) = (1 ^ 1) = 0 となり、arr3[3]（= 0）と一致するため、反転は不要です。
• (arr1[4] ^ arr2[4]) = (0 ^ 0) = 0 となり、arr3[4]（= 0）と一致するため、反転は不要です。
• (arr1[5] ^ arr2[5]) = (1 ^ 0) = 1 となり、arr3[5]（= 0）とは一致しないため、反転が必要です。
• (arr1[6] ^ arr2[6]) = (0 ^ 1) = 1 となり、arr3[6]（= 0）とは一致しないため、反転が必要です。

この例では、インデックス0、5、6の合計3箇所で反転が必要になります。反転回数の上限は p + q = 7 なので、3回の反転で十分に条件を満たせることが分かります。

アルゴリズム

1. (arr1[i] ^ arr2[i]) == arr3[i] の場合は反転不要のため、そのまま次の要素へ進みます。
2. (arr1[i] ^ arr2[i]) != arr3[i] の場合は反転が必要です。
   　a. arr3[i] == 0 の場合、次のいずれかの状態になっています。
   　　i. arr1[i] == 0 かつ arr2[i] == 0
   　　ii. arr1[i] == 1 かつ arr2[i] == 1
   　b. arr3[i] == 1 の場合、次のいずれかの状態になっています。
   　　i. arr1[i] == 0 かつ arr2[i] == 1
   　　ii. arr1[i] == 1 かつ arr2[i] == 0
3. 反転が必要な箇所では、arr1[i] と arr2[i] のどちらか一方を反転すればよいため、全体で必要な反転回数は p + q 以下に収まっている必要があります。これを超える場合は、条件を満たす解が存在しない（-1を返す）と判断できます。

C++での実装例

#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int getRequiredFlips(int *arr1, int *arr2, int *arr3, int n, int p, int q){
    int flips = 0;
    for (int i = 0; i < n; ++i) {
        if ((arr1[i] ^ arr2[i]) != arr3[i]) {
            ++flips;
        }
    }
    return flips <= (p + q) ? flips : -1;
}
int main(){
    int arr1[] = {1, 0, 1, 1, 0, 1, 0};
    int arr2[] = {0, 1, 0, 1, 0, 0, 1};
    int arr3[] = {0, 1, 1, 0, 0, 0, 0};
    int size = SIZE(arr1);
    cout << "Flips required: " << getRequiredFlips(arr1, arr2, arr3, size, 2, 5) << "\n";
    return 0;
}

実装は非常にシンプルです。各インデックスについて「arr1とarr2のXOR結果」と「arr3の値」を比較し、一致しなければカウンタを1増やします。すべての要素を走査した後、反転回数が p + q 以内であればその値を返し、超えている場合は -1 を返します。計算量はO(n)で、余分なメモリも不要という効率的なアルゴリズムです。

出力

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。

Flips required: 3

この結果から、必要な反転回数は3回であり、制約である p + q = 7 以内に収まっているため、この問題は解けることが確認できます。