概要

\(N \times M\) の数字グリッドから、面積がちょうど \(K\) になる長方形（\(h \times w = K\)）を選び、その中の数字和の最大値を求める問題です。

考察

重要な気づき

• 選べる長方形は「面積が \(K\)」という条件だけなので、候補となる形は \(K\) の約数ペア \((h, w)\)（\(h \times w = K\)） に限られます。
• 各 \((h, w)\) について、「サイズが固定された長方形の総和の最大値」を求めればよいです。

素朴な方法が厳しい理由

• 長方形の位置（左上・右下）を全探索し、さらにその中身を毎回足すと、1つの長方形の和を求めるのに \(O(hw)\) かかります。
• これを全位置でやると最悪で \(O(NM \cdot K)\) などになり、\(N,M \le 200\) では間に合いません。

解決策

• 2次元累積和を使うと、任意の長方形の和を \(O(1)\) で取り出せます。
• あとは \(K\) の約数ペアごとに全位置を走査して最大値を更新します。

アルゴリズム

1. 2次元累積和 \(ps\) を作る
   • \(ps[i+1][j+1]\) を「左上 \((0,0)\) から右下 \((i,j)\) までの長方形の総和」として構築します。
2. \(K\) の約数 \(d\) を \(1\) から \(\lfloor\sqrt{K}\rfloor\) まで列挙
   • \(d \mid K\) なら \((h,w)=(d, K/d)\) が候補。
   • 回転も別形状なので、\((K/d, d)\) も候補（同じなら1回だけ）。
3. 各候補 \((h,w)\) について最大長方形和を計算
   • \(h \le N, w \le M\) を満たすときだけ調べる。
   • 右下を \((i,j)\)（累積和配列上の添字）とすると、該当長方形の和は $\( \text{sum} = ps[i][j] - ps[i-h][j] - ps[i][j-w] + ps[i-h][j-w] \)$
   • 全ての位置を走査して最大値を取る。
4. 一度も条件を満たす長方形がなければ \(-1\)、あれば最大値を出力。

計算量

• 時間計算量:
  
  • 累積和の構築が \(O(NM)\)
    
  • 約数ペアは最大でも \(\sqrt{K}\) 個程度なので、各ペアで全位置を走査して \(O(NM)\)
    
  • 合計で \(O(NM\sqrt{K})\)（この制約では十分高速）
• 空間計算量: \(O(NM)\)（累積和配列）

実装のポイント

• 入力は各行が文字列なので、list(map(int, input().strip())) で各桁を数値化しています。

• 「ぴったりルールを満たす領域が存在しない」ケースのため、答えは最初 -1 にしておき、見つかったときだけ更新します。

• 約数列挙では \((d, K//d)\) と \((K//d, d)\) の両方を確認し、縦横の入れ替えを取りこぼさないようにします。

  ソースコード

import sys
import math

def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    grid = [list(map(int, input().strip())) for _ in range(N)]

    ps = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N):
        row_ps = ps[i + 1]
        prev_ps = ps[i]
        s = 0
        row = grid[i]
        for j in range(M):
            s += row[j]
            row_ps[j + 1] = prev_ps[j + 1] + s

    def max_rect(h, w):
        best = -1
        ps_local = ps
        for i in range(h, N + 1):
            psi = ps_local[i]
            psih = ps_local[i - h]
            for j in range(w, M + 1):
                v = psi[j] - psih[j] - psi[j - w] + psih[j - w]
                if v > best:
                    best = v
        return best

    ans = -1
    r = int(math.isqrt(K))
    for d in range(1, r + 1):
        if K % d != 0:
            continue
        h1, w1 = d, K // d
        if h1 <= N and w1 <= M:
            ans = max(ans, max_rect(h1, w1))
        if h1 != w1:
            h2, w2 = w1, h1
            if h2 <= N and w2 <= M:
                ans = max(ans, max_rect(h2, w2))

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。