C++で1の数が0の数より1つ多い最大部分行列の面積を求める方法

この記事では、0と1だけで構成された n×n の2次元行列が与えられたときに、「1の個数が0の個数よりちょうど1つ多い」部分行列のうち、面積（要素数）が最大になるものを求めるC++プログラムを解説します。

問題の例

入力

bin[N][N] = {
    {0, 1, 0, 0},
    {1, 1, 0, 0},
    {1, 0, 1, 1},
    {0, 1, 0, 1}
}

出力

9

説明

部分行列：
bin[1][0], bin[1][1], bin[1][2]
bin[2][0], bin[2][1], bin[2][2]
bin[3][0], bin[3][1], bin[3][2]

これが「1の数が0の数より1つ多い」という条件を満たす
最大の部分行列です。
0の個数 = 4
1の個数 = 5

解法アプローチ

素朴な方法：全部分行列の列挙

もっとも単純な発想は、行列から取り得るすべての部分行列を列挙し、その中で条件を満たすものの最大面積を返すことです。考え方はシンプルで実装も容易ですが、多重ループのネストが必要になり、時間計算量は O(n⁴) に達します。そのため、大きな行列に対しては実用的ではありません。

効率的な方法：左右の列を固定して1次元問題へ帰着

ここで紹介するのは、より効果的な手法です。まず行列の左端と右端の列を固定し、1を +1、0を −1 として各行ごとに値を累積していきます。こうすると、「1の数が0の数より1つ多い区間」を見つける問題は、「区間和が1となる最長の部分配列」を求める1次元問題に置き換えられます。

この1次元の最長部分配列問題は、ハッシュマップ（連想配列）を使って各累積和の最初の出現位置を記録することで、線形時間 O(n) で解けます。左右の列の組み合わせは O(n²) 通りあるため、全体の時間計算量は O(n³) となり、全探索よりも大幅に高速化できます。

C++による実装例

以下は、上記の解法の動作を示すサンプルプログラムです。

#include <bits/stdc++.h>
using namespace std;
#define SIZE 10

// 区間和が1となる最長の部分配列を求める関数
int lenOfLongSubarr(int row[], int n, int& startInd, int& finishInd){
    unordered_map<int, int> subArr;
    int sumVal = 0, maxSubArrLen = 0;
    for (int i = 0; i < n; i++) {
        sumVal += row[i];
        // 先頭からの累積和が1の場合
        if (sumVal == 1) {
            startInd = 0;
            finishInd = i;
            maxSubArrLen = i + 1;
        }
        else if (subArr.find(sumVal) == subArr.end())
            subArr[sumVal] = i;
        // 累積和が (sumVal - 1) となる位置が存在すれば更新
        if (subArr.find(sumVal - 1) != subArr.end()) {
            int currLen = (i - subArr[sumVal - 1]);
            if (maxSubArrLen < currLen)
                startInd = subArr[sumVal - 1] + 1;
            finishInd = i;
            maxSubArrLen = currLen;
        }
    }
    return maxSubArrLen;
}

// 最大の部分行列面積を求める関数
int largestSubmatrix(int bin[SIZE][SIZE], int n){
    int rows[n], maxSubMatArea = 0, currArea, longLen, startInd,
    finishInd;
    for (int left = 0; left < n; left++) {
        memset(rows, 0, sizeof(rows));
        for (int right = left; right < n; right++) {
            // right列目の値を行ごとの累積に加算（0なら-1、1なら+1）
            for (int i = 0; i < n; ++i){
                if(bin[i][right] == 0)
                    rows[i] -= 1;
                else
                    rows[i] += 1;
            }
            longLen = lenOfLongSubarr(rows, n, startInd, finishInd);
            currArea = (finishInd - startInd + 1) * (right - left + 1);
            if ((longLen != 0) && (maxSubMatArea < currArea)) {
                maxSubMatArea = currArea;
            }
        }
    }
    return maxSubMatArea;
}

int main(){
    int bin[SIZE][SIZE] = {
        { 1, 0, 0, 1 },
        { 0, 1, 1, 1 },
        { 1, 0, 0, 0 },
        { 0, 1, 0, 1 }
    };
    int n = 4;
    cout << "1の数が0の数より1つ多い最大部分行列の面積は "
         << largestSubmatrix(bin, n);
    return 0;
}

実行結果

1の数が0の数より1つ多い最大部分行列の面積は 9

まとめ

この問題のポイントは、2次元の部分行列の条件判定を「列のペアを固定 → 行方向の累積和を計算 → 区間和が1となる最長区間をハッシュマップで探索」という流れで1次元問題に落とし込むことです。これにより、素朴な全探索の O(n⁴) から O(n³) へと計算量を削減でき、より大きな行列にも対応できるようになります。