解法の概要

本課題は行列内の全ての部分行列の和の中で最大値を求めることを要求します。全ての部分行列を総当たりで列挙し和を計算する方法では、計算量がO(n^4)となり、nが大きい場合に効率が悪くなります。ここでは二次元累積和の技法を用いて計算プロセスを最適化します。

二次元累積和の基本概念

二次元累積和は前処理技術の一つで、任意の部分行列の和をO(1)時間で計算できるようにします。具体的な実装方法は以下の通りです：

1. 累積和配列の前処理：元の行列と同じサイズの二次元配列pref_sumを構築し、pref_sum[i][j]は行列の左上(1,1)から(i,j)までの部分行列の全要素の和を表します。
2. 部分行列和の計算：任意の部分行列(x1,y1)から(x2,y2)までの和は以下の式で高速に計算できます：

   sum = pref_sum[x2][y2] - pref_sum[x1-1][y2] - pref_sum[x2][y1-1] + pref_sum[x1-1][y1-1]

アルゴリズムの最適化

累積和配列を前処理で得た後も、全ての可能な部分行列を列挙する必要があります。計算量は依然としてO(n^4)ですが、各部分行列の和の計算時間がO(1)に減少するため、実際の実行効率は大幅に向上し、n=120程度のデータ規模では十分に処理可能です。

実装コード例

#include<iostream>
#include<algorithm>
using namespace std;

const int MAX_SIZE = 125;
int matrix[MAX_SIZE][MAX_SIZE];
int prefix_sum[MAX_SIZE][MAX_SIZE];
int dimension;
int max_result;

int main() {
    cin >> dimension;
    
    for (int row = 1; row <= dimension; row++) {
        for (int col = 1; col <= dimension; col++) {
            cin >> matrix[row][col];
            prefix_sum[row][col] = prefix_sum[row-1][col] + prefix_sum[row][col-1] 
                                  - prefix_sum[row-1][col-1] + matrix[row][col];
        }
    }

    max_result = matrix[1][1];
    
    for (int start_row = 1; start_row <= dimension; start_row++) {
        for (int start_col = 1; start_col <= dimension; start_col++) {
            for (int end_row = start_row; end_row <= dimension; end_row++) {
                for (int end_col = start_col; end_col <= dimension; end_col++) {
                    int current_sum = prefix_sum[end_row][end_col] 
                                   - prefix_sum[start_row-1][end_col] 
                                   - prefix_sum[end_row][start_col-1] 
                                   + prefix_sum[start_row-1][start_col-1];
                    max_result = max(max_result, current_sum);
                }
            }
        }
    }
    
    cout << max_result << endl;
    return 0;
}

コード解説

1. 定数定義と変数宣言：
   • MAX_SIZE：行列の最大次元を125に設定
   • matrix：入力された元の行列を格納
   • prefix_sum：計算された累積和行列
   • dimension：行列の実際の次元
   • max_result：最終結果（最大部分行列和）を保持
2. 累積和行列の構築：
   • 二重ループで行列の各要素を処理
   • prefix_sum[row][col] = prefix_sum[row-1][col] + prefix_sum[row][col-1] - prefix_sum[row-1][col-1] + matrix[row][col]：
     • prefix_sum[row-1][col]：上方の矩形の累積和
     • prefix_sum[row][col-1]：左方の矩形の累積和
     • prefix_sum[row-1][col-1]：重複計算された左上部分
     • matrix[row][col]：現在の要素値
3. 部分行列の列挙：
   • 四重ループで全ての可能な部分行列を列挙：
     • (start_row, start_col)：部分行列の左上座標
     • (end_row, end_col)：部分行列の右下座標
   • 累積和公式を用いて部分行列和を高速計算
4. 結果出力：
   • 発見された最大部分行列和を出力