概要

\(N \times M\) のグリッドから、面積がちょうど \(K\) となる長方形領域を選び、その中のポイント合計を最大化する問題です。面積 \(K\) を満たす長方形が存在しない場合は \(-1\) を出力します。

考察

重要な気づき

長方形領域の縦幅を \(h\)、横幅を \(w\) とすると、条件は \(h \times w = K\) です。つまり、\(K\) の約数のペア \((h, w)\) のうち、\(h \leq N\) かつ \(w \leq M\) を満たすものだけが候補になります。

素朴なアプローチの問題

もし全ての \((h, w, i, j)\) の組み合わせ（左上の位置 \((i, j)\) と サイズ \((h, w)\)）について各要素を1つずつ足し合わせると、1つの長方形あたり \(O(h \times w)\) かかり、全体として非常に大きな計算量になってしまいます。

解決策：二次元累積和

二次元累積和（2D Prefix Sum） を前計算しておけば、任意の長方形領域の合計を \(O(1)\) で求められます。これにより、各候補 \((h, w)\) について全ての配置位置を高速に調べることができます。

アルゴリズム

1. 二次元累積和の構築

   • \(\text{prefix}[i][j]\) を「グリッドの左上 \((1,1)\) から \((i,j)\) までの長方形に含まれるポイントの合計」と定義します。
   • 漸化式: \(\text{prefix}[i][j] = \text{prefix}[i-1][j] + \text{prefix}[i][j-1] - \text{prefix}[i-1][j-1] + \text{grid}[i][j]\)

2. \(K\) の約数列挙

   • \(d = 1, 2, \ldots, \lfloor\sqrt{K}\rfloor\) を調べ、\(K \% d = 0\) なら \((d, K/d)\) を候補ペアとして追加します。

3. 各ペア \((h, w)\) について探索

   • \(h \leq N\) かつ \(w \leq M\) を満たすペアのみ処理します。
   • 右下が \((i, j)\) となる \(h \times w\) の長方形の合計は次の式で \(O(1)\) 計算できます： $\(S = \text{prefix}[i][j] - \text{prefix}[i-h][j] - \text{prefix}[i][j-w] + \text{prefix}[i-h][j-w]\)$
   • 全ての有効な \((i, j)\) を走査し、最大値を更新します。

4. 結果の出力

   • 有効なペアが1つも存在しなければ \(-1\)、そうでなければ見つけた最大スコアを出力します。

具体例

例えば \(N=3, M=4, K=6\) のとき、\(6 = 1 \times 6, 2 \times 3, 3 \times 2, 6 \times 1\) が約数ペアです。このうち \(h \leq 3, w \leq 4\) を満たすのは \((2,3), (3,2), (1,6)\) を除く… のように、グリッドに収まるペアだけを調べます。\((1,6)\) は \(w=6 > M=4\) なので不可、\((6,1)\) は \(h=6 > N=3\) なので不可、\((2,3)\) と \((3,2)\) が有効です。

計算量

• 時間計算量: \(O(N \times M \times d(K))\)
  • \(d(K)\) は \(K\) の約数の個数です。累積和の構築に \(O(N \times M)\)、各約数ペアごとに全配置位置を調べるのに \(O(N \times M)\) かかります。\(K \leq 40000\) 程度では \(d(K)\) は高々数十なので十分高速です。
• 空間計算量: \(O(N \times M)\)（累積和テーブルの分）

実装のポイント

• 累積和の添字を 1-indexed にすると、\(i-h\) や \(j-w\) が \(0\) になるケースを自然に扱えて境界処理が楽になります。

• 約数列挙は \(\sqrt{K}\) まで調べれば十分です。\(d\) と \(K/d\) の両方を追加することを忘れないようにしましょう。

• 答えの初期値を \(-1\) にしておけば、有効なペアが存在しない場合にそのまま \(-1\) を出力できます。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    # Build prefix sum array
    grid = []
    for i in range(N):
        s = input_data[idx].decode(); idx += 1
        row = [int(c) for c in s]
        grid.append(row)
    
    # prefix[i][j] = sum of grid[0..i-1][0..j-1]
    prefix = [[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 += grid[i-1][j-1]
            prefix[i][j] = prefix[i-1][j] + row_sum
    
    # Find all (h, w) pairs where h * w = K, h <= N, w <= M
    ans = -1
    
    # Enumerate divisors of K
    divisors = []
    d = 1
    while d * d <= K:
        if K % d == 0:
            divisors.append(d)
            if d != K // d:
                divisors.append(K // d)
        d += 1
    
    for h in divisors:
        w = K // h
        if h > N or w > M:
            continue
        # Find maximum sum of h x w rectangle
        for i in range(h, N + 1):
            for j in range(w, M + 1):
                s = prefix[i][j] - prefix[i-h][j] - prefix[i][j-w] + prefix[i-h][j-w]
                if s > ans:
                    ans = s
    
    print(ans)

main()

この解説は claude4.6opus-thinking によって生成されました。