C++でマトリックス（行列）を反転した後に得られる最大スコアの求め方

0と1のみで構成される二次元マトリックス（行列）Aがあるとします。ここでいう「操作」とは、任意の行または列を選び、その行・列内のすべての値を反転させること、つまり0を1に、1を0に一括変更することを指します。任意の回数だけ操作を行った後、マトリックスの各行は2進数として解釈され、マトリックス全体のスコアはこれらの数値の総和となります。今回の課題は、このスコアとして考えられる最大値を求めることです。

例えば、入力が以下のようなマトリックスだった場合を見てみましょう。

最適な操作を行った結果、出力は 39 になります。これは反転後のマトリックスが次のようになるためです。

このとき各行が表す数値は 1111₂ = 15、1001₂ = 9、1111₂ = 15 となり、合計は 15 + 9 + 15 = 39 です。

解法のポイント：貪欲法（グリーディー法）

この問題を効率よく解くには、貪欲法を使います。重要な性質は次のとおりです。

• 最上位ビットは必ず1にできる： 各行を独立に反転できるため、すべての行の先頭（最上位桁）は必ず1にできます。最上位ビットは他のどの桁よりも重みが大きいため、これを優先的に1にするのが最善です。

• それ以外の列は多数決で決める： 先頭列が1になった状態では、ある列jについて「A[i][j] と A[i][0] が等しい行の数」を数えれば、反転によって作れる1の個数がわかります。cnt と n − cnt のうち大きい方の数だけ1にできます。

アルゴリズムの手順

• n := 行数、m := 列数とする

• ret := n × 2^{(m − 1)} を初期値とする（全行の最上位ビットが1になると仮定）

• j = 1 から m − 1 まで繰り返す

  • cnt := A[i][j] == A[i][0] を満たす行 i の個数

  • temp := 2^{(m − j − 1)} × max(cnt, n − cnt)

  • ret := ret + temp

• ret を返す

それでは、実際の実装例を見て理解を深めましょう。

C++実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int matrixScore(vector<vector<int>>& A) {
        int n = A.size();
        int m = A[0].size();
        int ret = (1 << (m - 1)) * n;
        for(int j = 1; j < m; j++){
            int cnt = 0;
            for(int i = 0; i < n; i++){
                cnt += (A[i][j] == A[i][0]);
            }
            int temp = ((1 << (m - (j + 1))) * max(cnt, n - cnt));
            ret += temp;
        }
        return ret;
    }
};
main(){
    vector<vector<int>> v = {{0,0,1,1},{1,0,1,0},{1,1,0,0}};
    Solution ob;
    cout << (ob.matrixScore(v));
}

入力

[[0,0,1,1],[1,0,1,0],[1,1,0,0]]

出力

39

この実装では、行・列を実際に反転させる処理を行わずに、ビット演算とカウントだけで最大スコアを計算しています。そのため計算量は O(n × m) と非常に効率的で、大きなマトリックスでも高速に動作します。実際に反転操作をシミュレーションする必要がない点が、この貪欲法アプローチの大きな利点といえるでしょう。