概要

この問題は、与えられたグリッドから長方形領域を選び、その領域内の数字の合計を最大化する問題です。ただし、領域のサイズは縦 \(h\) × 横 \(w\) で \(h \times w = K\) を満たす必要があります。

考察

素朴なアプローチでは、すべての可能な長方形領域を列挙し、その合計を計算すると、時間計算量が \(O(N^2 M^2)\) となり、\(N, M\) が最大200の場合、最悪で約 \(200^4 = 1.6 \times 10^9\) 回の計算が必要となり、実行時間制限に間に合いません。そこで、効率的に合計を計算するために、二次元累積和を用いることが重要です。また、\(K\) の約数の組 \((h, w)\) のみを考慮することで、探索する長方形のサイズを限定できます。

アルゴリズム

1. 前処理: 二次元累積和テーブル pre_sum を構築します。これにより、任意の長方形領域の合計を \(O(1)\) で計算できます。
   • pre_sum[i][j] は、グリッドの左上 \((0, 0)\) から右下 \((i-1, j-1)\) までの領域の合計を表します。
2. 約数の列挙: \(K\) の約数 \(h\) を列挙し、\(w = K / h\) が \(M\) 以下か確認します。これにより、探索する長方形のサイズ \((h, w)\) の組を取得します。
3. 最大値の探索: 各サイズ \((h, w)\) について、全ての可能な開始位置 \((i, j)\) を走査し、累積和を使って合計を計算します。最大値を見つけて出力します。

計算量

• 時間計算量: \(O(d \cdot N \cdot M)\)
  • \(d\) は \(K\) の約数の個数（最大でも約 \(2\sqrt{K}\) 程度）
  • \(N, M\) は最大200なので、十分高速です。
• 空間計算量: \(O(N \cdot M)\)
  • 二次元累積和テーブルの構築に必要なメモリ

実装のポイント

• 累積和テーブルは1-indexedで構築すると、境界条件の処理が簡単になります。

• \(K\) がグリッドの総サイズより大きい場合や、約数が存在しない場合は早期に \(-1\) を返します。

• 各約数に対して二重ループで開始位置を走査し、累積和から合計を \(O(1)\) で計算します。

  ソースコード

def main():
    import sys
    data = sys.stdin.read().splitlines()
    if not data:
        print(-1)
        return
        
    n, m, K = map(int, data[0].split())
    grid = []
    for i in range(1, 1 + n):
        grid.append(data[i].strip())
    
    total_cells = n * m
    if K > total_cells:
        print(-1)
        return
        
    factors = []
    for h in range(1, n + 1):
        if K % h == 0:
            w = K // h
            if 1 <= w <= m:
                factors.append((h, w))
                
    if not factors:
        print(-1)
        return
        
    pre_sum = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        row_sum = 0
        for j in range(1, m + 1):
            row_sum += int(grid[i-1][j-1])
            pre_sum[i][j] = pre_sum[i-1][j] + row_sum
            
    max_score = -1
    for h, w in factors:
        for i in range(0, n - h + 1):
            for j in range(0, m - w + 1):
                total = pre_sum[i+h][j+w] - pre_sum[i][j+w] - pre_sum[i+h][j] + pre_sum[i][j]
                if total > max_score:
                    max_score = total
                    
    print(max_score)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。