概要

\(N \times M\) のグリッドから、面積（マスの数）がちょうど \(K\) となる長方形領域を選び、その中の数値の合計を最大化する問題です。

考察

この問題を解くためのポイントは、「長方形のサイズを絞り込むこと」と「領域内の合計を高速に計算すること」の2点です。

1. 長方形のサイズの決定

選ぶ長方形の縦の長さを \(h\)、横の長さを \(w\) とすると、条件は \(h \times w = K\) です。 ここから以下のことが分かります。 - \(h\) は \(K\) の約数である必要がある。 - グリッドの範囲内に収まる必要があるため、\(1 \leq h \leq N\) かつ \(1 \leq w \leq M\) を満たす必要がある。

これらを満たす \((h, w)\) の組はそれほど多くありません。例えば \(N, M \leq 200\) の場合、最大でも数百通り程度です。

2. 領域内の合計計算（累積和）

長方形の左上と右下の座標を固定して毎回合計を計算すると、計算量が非常に大きくなってしまいます。 そこで、2次元累積和（または1次元累積和の応用）を利用します。 グリッドの左上 \((0, 0)\) から \((r, c)\) までの合計を \(P[r][c]\) としておけば、任意の長方形 \((r_1, c_1)\) から \((r_2, c_2)\) の合計は以下の式で \(O(1)\) で求められます。 $\(\text{Sum} = P[r_2][c_2] - P[r_1][c_2] - P[r_2][c_1] + P[r_1][c_1]\)$

3. 計算量を抑える工夫

今回のコードでは、2次元累積和を構築したあと、各 \(h\) に対して「高さ \(h\) の縦長の帯」の累積和を計算し、それを横方向にスライドさせることで効率的に最大値を探索しています。

アルゴリズム

1. 累積和の構築: グリッドの各マスの値を整数に変換し、2次元累積和テーブル \(P\) を作成します。
2. 長方形サイズの全探索: \(h\) を \(1\) から \(N\) までループさせます。
   • \(K\) が \(h\) で割り切れ、かつ商 \(w = K/h\) が \(M\) 以下であるか確認します。
3. 最大スコアの更新: 条件を満たす \((h, w)\) が見つかったら、そのサイズの長方形をグリッド内で動かし、合計スコアを計算します。
   • すべての可能な上端 \(r\) について、高さ \(h\) の区間の和を計算し、横方向の差分をとることで \(h \times w\) の合計を求めます。
4. 早期終了: スコアの理論上の最大値は \(9 \times K\) です。もし探索の途中でこの値に達した場合は、それ以上探索する必要がないため即座に出力して終了します。
5. 例外処理: 一度も条件を満たす長方形が見つからなかった場合は \(-1\) を出力します。

計算量

• 時間計算量: \(O(NM + D \cdot NM)\)
  • ここで \(D\) は \(K\) の約数の個数です（最大でも \(N\) 程度）。
  • \(N, M = 200\) のとき、\(NM = 40,000\) であり、全体でも数百万回の計算に収まるため、制限時間内に十分間に合います。
• 空間計算量: \(O(NM)\)
  • 累積和テーブルを保持するためのメモリが必要です。

実装のポイント

• ord(c) - 48: int(c) を使うよりも、文字コードの差分をとる方が Python では高速に数値変換できる場合があります。

• スライシングと zip: 内側のループで islice や zip を活用することで、Python のループ速度を補い、高速にスライド窓の計算を行っています。

• 範囲の絞り込み: start_h = (K + M - 1) // M とすることで、横幅 \(w\) が \(M\) を超えてしまうような小さな \(h\) を最初からスキップしています。

  ソースコード

import sys
from operator import sub
from itertools import islice

def solve():
    # Read all input data and split by whitespace
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Grid dimensions N, M and the required card count K
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    grid = input_data[3:]

    # Prefix sum array P where P[r][c] stores the sum of the grid from (0,0) to (r-1, c-1)
    # This allows O(1) sum calculation for any rectangle in the grid.
    P = [[0] * (M + 1) for _ in range(N + 1)]
    for r in range(N):
        row_str = grid[r]
        Pr = P[r]
        Pr1 = P[r+1]
        row_sum = 0
        for c in range(M):
            # ord(c) - 48 is an efficient way to convert a digit character to its integer value
            row_sum += ord(row_str[c]) - 48
            Pr1[c+1] = Pr[c+1] + row_sum

    max_score = -1
    # The maximum possible score for K cards is 9 * K
    limit_score = 9 * K
    
    # A valid rectangle must have dimensions (h, w) such that h * w = K.
    # Constraints require 1 <= h <= N and 1 <= w <= M.
    # This implies h must be a divisor of K and h >= K / M.
    start_h = (K + M - 1) // M
    
    # Iterate through all possible heights h that satisfy the card count rule
    for h in range(start_h, N + 1):
        if K % h == 0:
            w = K // h
            # For a fixed rectangle size (h, w), iterate through all possible top-left corners
            for r in range(h, N + 1):
                Pr = P[r]
                Prh = P[r-h]
                
                # T[c] represents the sum of a vertical segment of height h ending at row r
                # list(map(sub, Pr, Prh)) is an efficient way to compute T[c] = P[r][c] - P[r-h][c]
                T = list(map(sub, Pr, Prh))
                
                # The sum of an h x w rectangle ending at (r, c) is T[c] - T[c-w]
                # islice and zip are used to iterate through the sliding window sums efficiently
                Tw = islice(T, w, None)
                for tw, t0 in zip(Tw, T):
                    s = tw - t0
                    if s > max_score:
                        max_score = s
                        # If the theoretical maximum score is reached, exit early
                        if max_score == limit_score:
                            print(max_score)
                            return
    
    # Print the maximum score found, or -1 if no valid rectangle exists
    print(max_score)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。