C++で行列のインクリメント操作後に奇数値となるセルの数を求める方法

n 行 m 列の行列を考えます。この行列は、すべての要素が 0 で初期化されています。さらに、indices[i] = [ri, ci] の形式でインデックスのペアが与えられます。各ペア [ri, ci] に対して、行 ri に属するすべてのセルと列 ci に属するすべてのセルの値を 1 ずつ加算します。すべてのインデックスに対してこの操作を適用した後、値が奇数になっているセルの総数を求めるのがこの問題の目的です。

解法のステップ

この問題は、与えられた操作をそのままシミュレーションすることで解決できます。具体的な手順は以下の通りです。

• カウンタ odd を 0 で初期化し、変数 x にはインデックスリストのサイズを代入します。
• n × m の行列 mat を作成します（すべて 0 で初期化）。
• i を 0 から x − 1 までループさせます。
  • r = input[i][0]、c = input[i][1] を取り出します。
  • j を 0 から m − 1 までループし、mat[r][j] を 1 加算します。
  • j を 0 から n − 1 までループし、mat[j][c] を 1 加算します。
• i を 0 から n − 1、j を 0 から m − 1 までの二重ループで全セルを走査し、odd に「mat[i][j] と 1 のビットごとの AND」の結果（奇数なら 1、偶数なら 0）を加算します。
• 最後に odd を返します。

C++による実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
        int oddCells(int n, int m, vector<vector<int>>& in) {
        int odd = 0;
        int x = in.size();
        vector<vector<int>> mat(n, vector<int>(m));
        for(int i = 0; i < x; i++){
            int r = in[i][0];
            int c = in[i][1];
            for(int j = 0; j < m; j++){
                mat[r][j]++;
            }
            for(int j = 0; j < n; j++){
                mat[j][c]++;
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++) odd += mat[i][j] & 1;
        }
        return odd;
    }
};
main(){
    Solution ob;
    vector<vector<int>> c = {{0,1},{1,1}};
    cout << ob.oddCells(2,3,c);
}

入力

2
3
{{0,1},{1,1}}

出力

6

出力の解説

2 × 3 の行列に対して、(0, 1) と (1, 1) の 2 回の操作を適用すると、行列は次のように変化します。

初期状態:        (0,1) 適用後:     (1,1) 適用後:
0 0 0            1 2 1             1 3 1
0 0 0            0 1 0             1 3 1

最終的にすべてのセルの値が奇数（1 または 3）になるため、答えは 6 となります。

計算量について見てみると、各操作で 1 行と 1 列を更新するため O(x × (n + m))、最後の全セル走査に O(n × m) の時間が必要です。行列のサイズや操作回数がそれほど大きくなければ、この素直なシミュレーション手法で十分に高速に動作します。