C++で指定サイズのバイナリ部分行列の個数を求めるクエリ処理

この問題では、n×mのサイズを持つバイナリ行列bin[][]が与えられ、q個のクエリすべてに対する答えを求めます。各クエリ(x, y)に対しては、全要素がy（0または1）で構成されるx×xサイズの部分行列の個数を出力する必要があります。

問題の概要

与えられたサイズの部分行列のうち、0と1のどちらか一方の値だけで構成されているもの、すなわち全要素が0のみ、または全要素が1のみで構成される正方形部分行列の総数を数えます。

具体例で問題を確認しよう

入力

n = 3 , m = 4
bin[][] = {{ 1, 1, 0, 1},
{ 1, 1, 1, 0},
{ 0, 1, 1, 1}}
q = 1
q1 = (2, 1)

出力

2

出力の解説

サイズ2×2で全要素が1となる部分行列は、左上の座標が(0, 0)であるものと(1, 1)であるものの2つが存在します。

解法のアプローチ：動的計画法

この問題は動的計画法（Dynamic Programming）を用いて効率的に解けます。同じビット値だけで構成される最大の正方形部分行列の一辺の長さを記録するため、2次元配列DP[][]を用意します。DP[i][j]には、右下の要素の座標が(i, j)であり、かつ範囲内の全要素が同一の値であるような正方形部分行列の最大サイズが格納されます。

例えばDP[4][5] = 2であれば、bin[3][4]、bin[3][5]、bin[4][4]、bin[4][5]の4つの要素がすべて同じ値であることを意味します。

DP[i][j]を求める際は、次の2つの場合に分けて考えます。

ケース1：i = 0 または j = 0 の場合 → DP[i][j] = 1。行列の端では1×1の部分行列しか作れないためです。

ケース2：上記以外で、bin[i][j] = bin[i-1][j] = bin[i][j-1] = bin[i-1][j-1] が成り立つ場合 → DP[i][j] = min(DP[i][j-1], DP[i-1][j], DP[i-1][j-1]) + 1。隣接する3つのセルのDP値の最小値に1を加えることで、目的の正方形部分行列が拡張されていきます。例えばk = 2、つまり2×2の部分行列を考える場合は、bin[i][j] = bin[i][j-1] = bin[i-1][j] = bin[i-1][j-1] が成立するかを確認し、成立すればDP[i][j]を更新します。

ケース2の条件が満たされない場合は、デフォルト値としてDP[i][j] = 1を設定します。

DP[i][j]の値は、ビットが1（セット）の場合にも0（アンセット）の場合にも対応します。bin[i][j]の実際の値を調べることで、そのサイズがどちらのビットに属するかを判別できます。頻度を集計するために、0で構成される部分行列の頻度を格納するzeroFrequency配列と、1で構成される部分行列の頻度を格納するoneFrequency配列の2つの配列を作成します。

ソリューションの動作を示すプログラム：

実装例

#include <iostream>
using namespace std;
#define N 3
#define M 4

int min(int a, int b, int c) {
    if (a <= b && a <= c)
    return a;
    else if (b <= a && b <= c)
    return b;
    else
    return c;
}

int solveQuery(int n, int m, int bin[N][M], int x, int y){
    int DP[n][m], max = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 || j == 0)
            DP[i][j] = 1;
            else if ((bin[i][j] == bin[i - 1][j]) && (bin[i][j] == bin[i][j - 1]) && (bin[i][j] == bin[i - 1][j - 1])) {
                DP[i][j] = min(DP[i - 1][j], DP[i - 1][j - 1], DP[i][j - 1]) + 1;
                if (max < DP[i][j])
                max = DP[i][j];
            }
            else
            DP[i][j] = 1;
        }
    }
    int zeroFrequency[n+m] = { 0 }, oneFrequency[n+m] = { 0 };
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (bin[i][j] == 0)
            zeroFrequency[DP[i][j]]++;
            else
            oneFrequency[DP[i][j]]++;
        }
    }
    for (int i = max - 1; i >= 0; i--) {
        zeroFrequency[i] += zeroFrequency[i + 1];
        oneFrequency[i] += oneFrequency[i + 1];
    }
    if (y == 0)
    return zeroFrequency[x];
    else
    return oneFrequency[x];
}

int main(){
    int n = 3, m = 4;
    int mat[N][M] =
    {{ 1, 1, 0, 1},
    { 1, 1, 1, 0},
    { 0, 1, 1, 1}};
    int Q = 2;
    int query[Q][2] = {{ 2, 1}, { 1, 0}};
    for(int i = 0; i < Q; i++){
        cout<<"For Query "<<(i+1)<<": The number of Binary sub-matrices of Given size is "<<solveQuery(n, m, mat, query[i][0], query[i][1])<<"\n";
    }
    return 0;
}

出力結果

For Query 1: The number of Binary sub-matrices of Given size is 2
For Query 2: The number of Binary sub-matrices of Given size is 3

このアルゴリズムの時間計算量はO(n×m)、空間計算量はO(n+m)となります。前計算によって頻度表を作成しておくことで、複数のクエリに対しても高速に回答できる点が大きな利点です。