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

このチュートリアルでは、「1の個数が0の個数よりちょうど1つ多くなるような、面積が最大の部分行列」を見つけるプログラムについて解説します。

問題の概要

0と1のみで構成された2次元行列が与えられます。ここで求めたいのは、含まれる1の数が0の数よりも多い部分行列の中で、面積（行数 × 列数）が最大になるものです。

例えば、次のような4×4の行列を考えてみましょう。

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

この場合、条件を満たす最大の部分行列は左上 (1,1) から右下 (3,3) までの3×3の領域となり、その面積は9になります。

アルゴリズムの考え方

この問題を効率よく解くポイントは、0を-1に置き換えて考えることです。こうすると「1の数が0の数より1つ多い」という条件は、「要素の総和が1となる区間を探す」という問題に変換できます。

具体的な手順は以下の通りです。

1. 左端の列 left を固定し、右端の列 right を順に広げていきます。
2. 各列について、1なら+1、0なら-1として各行ごとに累積配列 temp を更新します。
3. temp の中で「総和が1になる最長の連続部分配列」を、ハッシュマップを使ったプレフィックスサム（累積和）の手法で求めます。
4. 得られた長さ（高さ）と列幅から面積を計算し、これまでの最大値より大きければ座標と面積を記録します。

ハッシュマップには「ある累積和が最初に出現したインデックス」を保存しておき、現在の累積和との差が1になる位置を参照することで、条件を満たす区間を高速に特定できます。これにより、各列ペアに対する処理は線形時間で完了します。

C++による実装例

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

// 総和が1となる最長の部分配列の長さを求める関数
int lenOfLongSubarr(int arr[], int n, int& start, int& finish) {
   unordered_map<int, int> um;
   int sum = 0, maxLen = 0;
   for (int i = 0; i < n; i++) {
      sum += arr[i];
      if (sum == 1) {
         start = 0;
         finish = i;
         maxLen = i + 1;
      }
      else if (um.find(sum) == um.end()) um[sum] = i;
      if (um.find(sum - 1) != um.end()) {
         if (maxLen < (i - um[sum - 1])) start = um[sum - 1] + 1;
         finish = i;
         maxLen = i - um[sum - 1];
      }
   }
   return maxLen;
}

// 最大面積の部分行列を求める関数
void largestSubmatrix(int mat[SIZE][SIZE], int n) {
   int finalLeft, finalRight, finalTop, finalBottom;
   int temp[n], maxArea = 0, len, start, finish;
   for (int left = 0; left < n; left++) {
      memset(temp, 0, sizeof(temp));
      for (int right = left; right < n; right++) {
         for (int i = 0; i < n; ++i)
         temp[i] += mat[i][right] == 0 ? -1 : 1;
         len = lenOfLongSubarr(temp, n, start, finish);
         if ((len != 0) && (maxArea < (finish - start + 1) * (right - left + 1))) {
            finalLeft = left;
            finalRight = right;
            finalTop = start;
            finalBottom = finish;
            maxArea = (finish - start + 1) * (right - left + 1);
         }
      }
   }
   cout << "(Top, Left): (" << finalTop << ", " << finalLeft << ")\n";
   cout << "(Bottom, Right): (" << finalBottom << ", " << finalRight << ")\n";
   cout << "Maximum area: " << maxArea;
}

int main() {
   int mat[SIZE][SIZE] = {
      { 1, 0, 0, 1 },
      { 0, 1, 1, 1 },
      { 1, 0, 0, 0 },
      { 0, 1, 0, 1 }
   };
   int n = 4; largestSubmatrix(mat, n);
   return 0;
}

実行結果

(Top, Left): (1, 1)
(Bottom, Right): (3, 3)
Maximum area: 9

処理の流れと計算量

main 関数では4×4のサンプル行列を定義し、largestSubmatrix を呼び出しています。実行結果から、行1〜3・列1〜3の範囲にある3×3の部分行列が条件を満たし、その面積が9であることが分かります。

計算量については、左右の列の組み合わせを列挙するのに O(n²)、それぞれの組み合わせで最長部分配列を求めるのに O(n) かかるため、全体の時間計算量は O(n³) となります。追加で使用するのは累積配列とハッシュマップ程度なので、空間計算量は O(n) です。

全ての部分行列を素朴に調べる O(n⁴) やそれ以上のアプローチと比べると、0を-1に変換して累積和とハッシュマップを活用するこの手法は、かなり効率的であると言えます。