概要

\(N \times N\) のグリッドから \(K \times K\) の部分正方形を選び、その中の最大要素を1つ取り除かれた後の合計値（＝部分正方形の合計 − 最大値）を最大化する問題です。

考察

青木君の最適戦略

青木君は選ばれた \(K \times K\) 区域内のちょうど1マスを \(0\) に変更します。区域内の合計を最小化したいので、景観スコアが最大のマスを選んで \(0\) にするのが最適です。

したがって、区域 \((r, c)\) を選んだときの満足度は：

\[\text{満足度} = (\text{区域内の合計}) - (\text{区域内の最大値})\]

素朴なアプローチとその問題点

各 \(K \times K\) 区域について合計と最大値を愚直に計算すると、区域は \((N-K+1)^2\) 個あり、各区域の計算に \(O(K^2)\) かかるため、全体で \(O((N-K+1)^2 \cdot K^2) = O(N^2 K^2)\) となります。\(N = 1000\) のとき最悪 \(O(10^{12})\) 程度になり、TLE します。

高速化の方針

• 区域内の合計: 2次元累積和を前計算すれば \(O(1)\) で求められます。
• 区域内の最大値: 2次元スライディングウィンドウ最大値を使えば、全区域の最大値を \(O(N^2)\) で前計算できます。

アルゴリズム

1. 2次元累積和（部分正方形の合計を \(O(1)\) で取得）

\(\text{prefix}[i][j]\) を左上 \((0,0)\) から \((i-1, j-1)\) までの合計として定義します。任意の矩形の合計は包除原理で \(O(1)\) で計算できます。

2. 2次元スライディングウィンドウ最大値

これは2段階で行います：

ステップ1: 行方向のスライディングウィンドウ最大値

各行 \(i\) について、幅 \(K\) のウィンドウで最大値を求めます。単調減少デック（monotone deque）を使い、各行 \(O(N)\) で処理します。

\[\text{row\_max}[i][j] = \max(A[i][j], A[i][j+1], \ldots, A[i][j+K-1])\]

ステップ2: 列方向のスライディングウィンドウ最大値

\(\text{row\_max}\) の各列について、高さ \(K\) のウィンドウで最大値を求めます。

\[\text{block\_max}[r][c] = \max(\text{row\_max}[r][c], \text{row\_max}[r+1][c], \ldots, \text{row\_max}[r+K-1][c])\]

これにより \(\text{block\_max}[r][c]\) は左上 \((r, c)\) の \(K \times K\) 区域内の最大値になります。

3. 答えの計算

全ての区域 \((r, c)\) について以下を計算し、最大値を求めます：

\[\text{満足度} = \text{subgrid\_sum}(r, c) - \text{block\_max}[r][c]\]

計算量

• 時間計算量: \(O(N^2)\)
  • 累積和の構築: \(O(N^2)\)
  • 2次元スライディングウィンドウ最大値: \(O(N^2)\)（各行・各列で線形）
  • 全区域の走査: \(O((N-K+1)^2)\)
• 空間計算量: \(O(N^2)\)

実装のポイント

• 単調デック（monotone deque）: スライディングウィンドウ最大値の核となるデータ構造です。デックの先頭が常にウィンドウ内の最大値のインデックスを保持するよう、新しい要素を追加するたびに末尾から小さい要素を除去し、ウィンドウから外れた先頭を除去します。

• 2段階に分ける: 2次元の最大値を直接求めるのではなく、行方向 → 列方向と2回に分けることで、1次元のスライディングウィンドウ問題に帰着できます。

• 景観スコアが \(0\) 以上: 青木君は必ず1マスを \(0\) にしなければならないため、全マスが \(0\) の区域を選んでも満足度は \(0\) です。負にはなりません。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    A = []
    for i in range(N):
        row = []
        for j in range(N):
            row.append(int(input_data[idx])); idx += 1
        A.append(row)
    
    # Prefix sum for computing sum of any K×K subgrid
    # prefix[i][j] = sum of A[0..i-1][0..j-1]
    prefix = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(N):
            prefix[i+1][j+1] = A[i][j] + prefix[i][j+1] + prefix[i+1][j] - prefix[i][j]
    
    def subgrid_sum(r1, c1, r2, c2):
        # sum of A[r1..r2][c1..c2] (0-indexed, inclusive)
        return prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]
    
    # For each K×K subgrid starting at (r, c) (0-indexed),
    # the satisfaction = sum_of_subgrid - max_element_in_subgrid
    # Because Aoki will remove the maximum element.
    
    # We need to compute the maximum element in each K×K subgrid efficiently.
    # We can use 2D sliding window maximum.
    
    # Step 1: For each row, compute sliding window max of width K
    # row_max[i][j] = max of A[i][j..j+K-1]
    
    from collections import deque
    
    # Row-wise sliding window max
    # row_max[i][j] for j in range(N-K+1): max of A[i][j..j+K-1]
    row_max = [[0] * (N - K + 1) for _ in range(N)]
    
    for i in range(N):
        dq = deque()
        for j in range(N):
            while dq and dq[0] < j - K + 1:
                dq.popleft()
            while dq and A[i][dq[-1]] <= A[i][j]:
                dq.pop()
            dq.append(j)
            if j >= K - 1:
                row_max[i][j - K + 1] = A[i][dq[0]]
    
    # Step 2: For each column of row_max, compute sliding window max of height K
    # block_max[r][c] = max of row_max[r..r+K-1][c] = max of K×K block starting at (r,c)
    
    num_cols = N - K + 1
    num_rows = N - K + 1
    block_max = [[0] * num_cols for _ in range(num_rows)]
    
    for c in range(num_cols):
        dq = deque()
        for i in range(N):
            while dq and dq[0] < i - K + 1:
                dq.popleft()
            while dq and row_max[dq[-1]][c] <= row_max[i][c]:
                dq.pop()
            dq.append(i)
            if i >= K - 1:
                block_max[i - K + 1][c] = row_max[dq[0]][c]
    
    # Now compute the answer
    ans = -1
    for r in range(num_rows):
        for c in range(num_cols):
            s = subgrid_sum(r, c, r + K - 1, c + K - 1)
            satisfaction = s - block_max[r][c]
            if satisfaction > ans:
                ans = satisfaction
    
    print(ans)

main()

---

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