C++でバイナリ行列を最大K回反転したときの最大スコアを求める方法

この記事では、0と1(ブール値)で構成される2次元配列 arr[] と整数 K が与えられたとき、バイナリ行列を最大 K 回反転した後の最大スコアを求めるプログラムを C++ で作成します。

問題の説明

2次元配列と K 回までの操作が与えられます。各操作では、任意の行または列を選び、その行(または列)に含まれるすべての要素を反転します(0 を 1 へ、1 を 0 へ)。操作の選択は、K 回の反転を行った後に、行列の各行が表す2進数の値が最大になるように行います。そして、各行で作られる数値の合計を答えとして返します。

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

入力

arr[][] = {
    {1, 0, 0},
    {0, 1, 1},
    {1, 0, 1}
}
K = 2

出力

19

解説

反転は2回行います。

1回目の反転: 2行目の要素を反転します。行列は次のようになります。

{{1, 0, 0},
{1, 0, 0},
{1, 0, 1}}

2回目の反転: 2列目の要素を反転します。行列は次のようになります。

{{1, 1, 0},
{1, 1, 0},
{1, 1, 1}}

このとき、各行が表す数値はそれぞれ 6、6、7 となります。

最大合計 = 6 + 6 + 7 = 19

解法アプローチ

この問題を解くうえでの重要なポイントは、左端の列(最上位ビット)を優先的に 1 にすることです。i 番目の列に置かれた 1 は 2^{(col−i−1)} という重みでスコアに寄与するため、1つのセットビットとしては最も大きな価値を持ちます。したがって、合計を最大化するには、左端の列にできるだけ多くの 1(セットビット)を集める必要があります。そのうえで、各行の残りの要素についても判断を行っていきます。

行を反転すべきか列を反転すべきかは、次のように判断します。

• ある行の先頭要素が 0 の場合、その行を反転すれば先頭ビットが 1 になり、スコアを大きく伸ばせます。
• ある列に含まれる 0 の数が 1 の数より多い場合、その列を反転することでその列の 1 の数を増やせます。

本解法では、反転候補となる行の情報を管理するために map データ構造を使用します。

解法を実装したC++プログラム

#include <bits/stdc++.h>
using namespace std;
const int row = 3;
const int col = 3;
int MaxSumAfterFlip(int mat[row][col], int K) {
    map<int, int> flipValues;
    int updateVal, MaxSum = 0;
    // 先頭列が 0 の行を反転候補として記録
    for (int i = 0; i < row; ++i) {
        if (mat[i][0] == 0) {
            updateVal = 0;
            for (int j = 1; j < col; ++j)
                updateVal = updateVal + mat[i][j] * pow(2, col - j- 1);
            flipValues[updateVal] = i;
        }
    }
    // 候補の行を順に反転
    map<int, int>::iterator it = flipValues.begin();
    while (K > 0 && it != flipValues.end()) {
        int updateIndex = it->second ;
        for (int j = 0; j < col; ++j)
            mat[updateIndex][j] = (mat[updateIndex][j] + 1) % 2;
        it++;
        K--;
    }
    // 列ごとに 0 と 1 の数を比較してスコアを計算
    MaxSum = 0;
    int zeros, ones = 0;
    for (int j = 0; j < col; ++j) {
        zeros = ones = 0;
        for (int i = 0; i < row; ++i) {
            mat[i][j] == 0 ? zeros++ : ones++;
        }
        if (K > 0 && zeros > ones) {
            MaxSum += zeros * pow(2, (col - j - 1));
            K--;
        }
        else
            MaxSum += ones * pow(2, (col - j - 1));
    }
    return MaxSum;
}
int main() {
    int mat[row][col] = {{1, 0, 0 },{0, 1, 1},{1, 0, 1}};
    int K = 2;
    cout<<"The Maximum score after flipping the matrix atmost K times is "<<MaxSumAfterFlip(mat, K);
    return 0;
}

出力

The Maximum score after flipping the matrix atmost K times is 19

プログラムの動作解説

このプログラムは、次のステップで最大スコアを求めます。

1. 反転候補の収集: 先頭列(最上位ビット)が 0 になっている行を検出し、その行の残りのビットで構成される値を計算して map に登録します。map はキー(値)の昇順に要素を保持するため、先頭から順に候補行を取り出して処理できます。
2. 行の反転: 残り反転回数 K がある間、map から行インデックスを取り出し、その行の全要素を反転して先頭ビットを 1 にします。
3. 列単位での評価: 各列について 0 と 1 の数を数えます。0 の方が多く、まだ反転回数が残っている場合は「その列を反転したもの」とみなして 0 の数 × ビットの重みを加算し、そうでなければ 1 の数 × 重みを加算します。

このアルゴリズムの計算量は O(row × col) であり、行列のサイズに対して線形時間で動作します。

まとめ

バイナリ行列の反転問題では、「最上位ビットにあたる左端の列を優先して 1 にする」という貪欲な方針が鍵となります。map を活用して反転候補の行を管理し、その後は列ごとに 0 と 1 の数を比較することで、最大 K 回の反転で得られる最大スコアを効率的に求めることができます。