概要

\(N \times M\) のグリッド上で、ちょうど \(K\) マスからなる長方形領域を選び、含まれる数字の合計を最大化する問題。

考察

この問題では、選ぶ長方形領域の面積がちょうど \(K\) である必要があります。つまり、縦の長さ \(h\) と横の長さ \(w\) について \(h \times w = K\) が成り立つ必要があります。

まず考えつくのは、すべての可能な \(h, w\) の組み合わせを試すことですが、\(K\) の約数を全探索することで候補を絞ることができます。\(h\) が \(K\) の約数であれば \(w = K/h\) となり、\(w\) が \(M\) 以下であるかどうかを確認すればよいです。

次に、それぞれの \(h, w\) の組について、グリッド内でのすべての位置における \(h \times w\) 長方形の和を求め、その最大値を記録します。しかし、単純に毎回長方形内の要素を足すと、計算量が多くなりすぎて間に合いません。

そこで、二次元累積和（いわゆる2D累積和）を用いることで、任意の長方形範囲の和を高速に求めることを可能にします。これにより、全体の計算量を大きく削減できます。

アルゴリズム

1. 入力処理:

   • グリッドを数値の二次元配列として読み込む。

2. 約数の列挙:

   • \(h = 1\) から \(N\) まで走査し、\(K\) が \(h\) で割り切れる場合、\(w = K/h\) とする。
   • \(w \leq M\) であれば、\((h, w)\) を候補として保存する。

3. 二次元累積和の構築:

   • 通常の累積和を2次元に拡張したもの。
   • acc[i][j] には、\((0, 0)\) から \((i-1, j-1)\) までの長方形領域の合計が格納される。
   • 更新式: $\( \text{acc}[i][j] = \text{grid}[i-1][j-1] + \text{acc}[i-1][j] + \text{acc}[i][j-1] - \text{acc}[i-1][j-1] \)$

4. 任意の長方形和の取得関数:

   • 関数 get_sum(x1, y1, x2, y2) で、\((x1, y1)\) から \((x2-1, y2-1)\) までの和を \(O(1)\) で取得できる。

5. 全探索と最大値更新:

   • 各候補 \((h, w)\) に対して、グリッド内で取りうるすべての位置 \((i, j)\) について、長方形和を計算し、最大値を更新していく。

6. 出力:

   • 候補が一つもなければ \(-1\) を出力。
   • それ以外の場合は得られた最大スコアを出力。

計算量

• 時間計算量: \(O(d(K) \cdot N \cdot M)\)
  （\(d(K)\) は \(K\) の約数の個数。最大でも数百程度）
• 空間計算量: \(O(N \cdot M)\)
  （二次元累積和テーブルのサイズ）

実装のポイント

• 二次元累積和のインデックス管理に注意すること（1-indexedで扱うことが多い）
• get_sum の引数が「半開区間」であることに注意（終端は含まない）
• \(h \times w = K\) を満たす組が存在しないケースを忘れずに判定すること

## ソースコード

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    
    # グリッド読み込み
    S = data[3:3+N]
    grid = []
    for i in range(N):
        row = list(map(int, list(S[i])))
        grid.append(row)
    
    # 約数列挙: K = h * w となる h, w の組を求める
    candidates = []
    for h in range(1, N+1):
        if K % h == 0:
            w = K // h
            if w <= M:
                candidates.append((h, w))
    
    if not candidates:
        print(-1)
        return
    
    # 二次元累積和の構築
    # acc[i][j] = (0,0) から (i-1,j-1) までの長方形和
    acc = [[0]*(M+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(M):
            acc[i+1][j+1] = grid[i][j] + acc[i+1][j] + acc[i][j+1] - acc[i][j]
    
    def get_sum(x1, y1, x2, y2):
        # (x1,y1) から (x2-1,y2-1) の長方形和を返す
        return acc[x2][y2] - acc[x1][y2] - acc[x2][y1] + acc[x1][y1]
    
    max_score = -1
    for h, w in candidates:
        for i in range(N - h + 1):
            for j in range(M - w + 1):
                current = get_sum(i, j, i+h, j+w)
                if current > max_score:
                    max_score = current
    
    print(max_score)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。