C++で指定された合計値を持つ部分行列を検索する方法

問題概要

この問題では、N×Nのサイズを持つ2次元行列と、sum（合計値）およびsize（サイズ）という2つの変数が与えられます。私たちのタスクは、指定された合計値を持つ部分行列を見つけることです。

具体的には、要素の合計がsumと等しくなるような、size×sizeのサイズの部分行列を探します。

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

入力 : mat[][] = {
   {1, 5, 7, 9},
   {2, 4, 6, 8},
   {1, 2, 5, 6},
   {3, 6, 9, 3}
}
sum = 22
Size = 2
出力 : YES

説明 −

合計が22となるサイズkの部分行列は以下の通りです。
{5, 7}
{4, 6}

解法アプローチ

この問題に対する最も単純な解決策は、考えられるすべてのsize×sizeの部分行列を生成し、それぞれの合計を計算して、与えられた合計値と比較する方法です。一致していればtrueを返します。

もう一つのより効率的なアプローチは、動的計画法（DP）の概念を利用する方法です。このアプローチでは、現在のインデックスまでの累積和を格納するDP配列を作成します。つまり、DP[i][j]には、行インデックス0からi、列インデックス0からjまでの範囲に含まれる全要素の合計が格納されます。

このDP配列を利用すると、任意の開始インデックスと終了インデックスの間の領域の合計を、次の式でO(1)で計算することができます。

$$\mathrm{sum((i_s,j_s)\:to\:(i_e,j_e))\:=\:DP[i_s][i_s]\:+\:DP[i_e][i_e]\:-\:DP[i_s][i_e]\:-\:DP[i_e][i_s]}$$

アルゴリズム

ステップ1 − サイズ(n+1)×(n+1)のDP行列を作成します。

ステップ2 − 行列の各要素について、現在のインデックスまでの累積和を求めます。

ステップ3 − 0からnまでのすべてのインデックスについて、上記の公式を用いてsize×sizeの部分行列の合計を計算し、currSumに格納します。

ステップ4 − currSum == sum の場合、trueを返します。

ステップ5 − 条件を満たす部分行列が存在しない場合はfalseを返します。

実装例

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

#include <iostream>
using namespace std;
#define N 4
bool findSubMatWithSum(int size, int sum, int mat[N][N]){
   int DP[N + 1][N + 1];
   for (int i = 0; i < N; i++)
   for (int j = 0; j < N; j++)
   DP[i + 1][j + 1] = DP[i + 1][j] + DP[i][j + 1] - DP[i][j] + mat[i][j];
   int currSum = 0;
   for (int i = 0; i < N; i++)
   for (int j = 0; j < N; j++) {
      currSum = DP[i][j] + DP[(i + size)][(j + size)] - DP[(i + size)][j] - DP[i][(j + size)];
      if (currSum == sum)
      return true;
   }
   return false;
}
int main(){
   int mat[N][N] = { { 1, 5, 7, 9 },
   { 2, 4, 6, 8 },
   { 1, 2, 5, 6 },
   { 3, 6, 9, 3 } };
   int size = 2;
   int sum = 22;
   if (findSubMatWithSum(size, sum, mat))
      cout<<"Sub-Matrix of given size having the given sum is possible!";
   else
     cout<<"Sub-Matrix of given size having the given sum is not possible!";
}

出力

Sub-Matrix of given size having the given sum is possible!

計算量の分析

累積和（DPテーブル）を事前に計算しておくことで、任意の部分行列の合計をO(1)で取得できます。DPテーブルの構築にはO(N²)、すべての候補位置のチェックにもO(N²)しかかからないため、全体の時間計算量はO(N²)となります。

一方、単純な全探索アプローチでは、各部分行列の合計計算にO(size²)が必要となるため、全体でO(N² × size²)の計算量になります。DPを活用することで、特にsizeが大きい場合に処理速度を大幅に向上させることができるのです。