C++で行列の行・列の最大XOR値を求める方法

この問題では、サイズ n × n の行列が与えられます。行全体または列全体のXOR値のうち最大のものを計算するプログラムを作成するのがタスクです。

具体例を使って問題を理解しましょう。

入力 −

N = 3
mat[N][N] = {{4, 9, 1},
{2, 8, 3},
{10, 12, 11}}

出力 −

13

説明 −

Row1: 4^9^1 = 12
Row2: 2^8^3 = 9
Row3: 10^12^11 = 13
Col1: 4^2^10 = 12
Col2: 9^8^12 = 13
Col3: 1^3^11 = 9

この例では、すべての行と列のXORを計算し、その中で最大の値である 13 を出力しています。

解決アプローチ

この問題を解くには、行列のすべての行と列のXORを計算し、その最大値を求めます。

行と列のXORを求める1つの方法は、行列を2回走査することです。1回目は行方向、2回目は列方向に走査します。

しかし、正方行列であれば、1回の走査で同じことを実現できます。外側のループの各反復において、行方向と列方向の両方を同時に処理するのです。

具体的には、同じ反復の中で mat[i][j] を使って行方向の要素にアクセスし、mat[j][i] を使って列方向の要素にアクセスします。

この方法の計算量は O(n²) となり、行列の各要素をちょうど1回ずつ訪れるだけで済むため、非常に効率的です。

実装例

この解法を示すプログラムは以下の通りです。

#include<iostream>
using namespace std;
const int MAX = 1000;
int maxRCXOR(int mat[][MAX], int N){
    int rowXOR, colXOR;
    int maxXOR = 0;
    for (int i = 0 ; i < N ; i++){
        rowXOR = 0, colXOR = 0;
        for (int j = 0 ; j < N ; j++){
            rowXOR = rowXOR^mat[i][j];
            colXOR = colXOR^mat[j][i];
        }
        if (maxXOR < max(rowXOR, colXOR))
            maxXOR = max(rowXOR, colXOR);
    }
    return maxXOR;
}
int main() {
    int N = 3;
    int matrix[][MAX]= {
        {4, 9, 1},
        {2, 8, 3},
        {10, 12, 11}
    };
    cout<<"行XORと列XORの最大値は "<<maxRCXOR(matrix,N);
    return 0;
}

出力

行XORと列XORの最大値は 13

プログラムでは、外側のループで行インデックス i を処理する際に、内側のループで行 i の要素（mat[i][j]）と列 i の要素（mat[j][i]）のXORを同時に計算しています。これにより、行列を1回走査するだけで行と列の両方のXOR値が得られ、最終的に最大値を返します。