C++で各行から数値を選択し、XORが0より大きくなるようにできるかを判定する方法

問題の概要

N × M の2次元配列が与えられたとします。この課題は、各行から1つずつ数値を選択し、選んだ要素のXOR（排他的論理和）が0以外（0より大きい値）になるようにできるかどうかを判定することです。例えば、次のような行列を考えてみましょう。

この場合、2行目の最後の要素以外が7と10で異なるため、XORを計算すると0以外の値になります。

解法のアプローチ

この問題の解法は非常にシンプルです。以下の手順で判定できます。

1. まず、各行の最初の列の要素のXORを計算します。その結果が0以外であれば、答えは「可能」です。
2. XORが0だった場合は、いずれかの行に2つ以上の異なる要素が含まれているかどうかを確認します。含まれていれば、その行で選ぶ要素を変更することでXORを0以外にできるため、やはり「可能」です。
3. 上記のどちらの条件も満たされない場合は、「不可能」です。

考え方のポイント

なぜこの判定で正しいのでしょうか。各行の最初の列の要素のXORがすでに0以外であれば、そのまま選択すればよいからです。一方、XORが0の場合でも、ある行に異なる要素が2つ以上存在すれば、そのうちの1つに選び替えることでXORの値は必ず変化します。逆に、すべての行が同一の値のみで構成されており、かつ最初の列のXORが0であれば、どのように選んでもXORは0のままになってしまいます。

サンプルコード

#include<iostream>
using namespace std;
#define N 2
#define M 3
bool isXORnonZero(int matrix[N][M]) {
    int xor_value = 0;
    for (int i = 0; i < N; i++) {
        xor_value ^= matrix[i][0];
    }
    if (xor_value != 0)
        return true;
    for (int i = 0; i < N; i++) {
        for (int j = 1; j < M; j++) {
            if (matrix[i][j] != matrix[i][0])
                return true;
        }
    }
    return false;
}
int main() {
    int mat[N][M] = {
        { 7, 7, 7 },
        { 10, 10, 7 }
    };
    if (isXORnonZero(mat))
        cout << "XOR has non-zero value";
    else
        cout << "XOR has zero value";
}

出力

XOR has non-zero value

まとめ

このアルゴリズムの計算量はO(N × M)です。行列全体を最大1回走査するだけで判定が完了するため、非常に効率的です。XORの性質（同じ値同士のXORは0になる、異なる値を1つ選び替えると結果が必ず変化する）を理解していれば、直感的に導き出せる解法と言えます。