概要

\(N \times N\) のグリッドから \(K \times K\) の正方形領域を選び、その領域内の「（合計値）－（最大値）」を最大化する問題です。 ライバルの青木君は、高橋君が選んだ領域の中で最もスコアが高いマスを \(0\) に書き換えることで、合計値を最小化（妨害）しようとするため、高橋君はあらかじめそれを考慮して領域を選択する必要があります。

考察

1. 満足度の数式化

青木君は領域内のスコアの合計を最小化するために、その領域内で最もスコアが大きいマスを \(0\) に変更します。 したがって、ある \(K \times K\) の領域を選んだときの満足度は以下のようになります。 $\(\text{満足度} = (\text{領域内の全マスの合計}) - (\text{領域内のマスの最大値})\)\( 高橋君の目的は、すべての可能な \)K \times K\( 領域（全部で \)(N-K+1)^2$ 個）についてこの値を計算し、その最大値を求めることです。

2. 素朴な方法の問題点

各領域について合計と最大値を愚直に計算すると、1つの領域あたり \(O(K^2)\) かかります。領域の数は約 \(N^2\) 個あるため、全体の計算量は \(O(N^2 K^2)\) となります。 \(N=1000\) の場合、\(N^4 = 10^{12}\) となり、実行制限時間に間に合いません。そのため、合計値と最大値をより効率的に求める必要があります。

3. 効率化のアプローチ

• 合計値の計算: 「2次元累積和」を用いることで、任意の \(K \times K\) 領域の合計を \(O(1)\) で計算できます。
• 最大値の計算: 「2次元スライディングウィンドウ最大値」という手法を用います。これは、まず各行に対して横方向のウィンドウ最大値を求め、その結果に対して縦方向にウィンドウ最大値を適用することで、 \(O(N^2)\) で全領域の最大値を求める手法です。

アルゴリズム

1. 2次元累積和の準備 グリッド \(A\) に対して累積和 \(S\) を計算します。これにより、左上 \((r, c)\) から右下 \((r+K-1, c+K-1)\) までの合計を \(S_{r+K, c+K} - S_{r, c+K} - S_{r+K, c} + S_{r, c}\) として高速に求められます。

2. 2次元スライディングウィンドウ最大値 各 \(K \times K\) 領域の最大値を以下の2ステップで求めます。

   • ステップ1（横方向）: 各行について、長さ \(K\) の連続する要素の最大値を求めます。
   • ステップ2（縦方向）: ステップ1の結果（各行の最大値が並んだもの）に対し、列方向に長さ \(K\) の連続する要素の最大値を求めます。

   ウィンドウ最大値の計算には、デック（両端キュー）を使う方法や、ブロックに分けて「前向き最大値」と「後ろ向き最大値」を組み合わせる方法（Disjoint Sparse Tableに近い考え方）があり、後者はPythonなどの言語で高速に動作します。

3. 最大満足度の算出 すべての \((r, c)\) について、「合計値 － 最大値」を計算し、その中の最大値を出力します。

計算量

• 時間計算量: \(O(N^2)\)
  • 2次元累積和の構築に \(O(N^2)\)
  • 2次元スライディングウィンドウ最大値の計算に \(O(N^2)\)
  • 全領域の走査に \(O(N^2)\)
• 空間計算量: \(O(N^2)\)
  • 累積和や各領域の最大値を保持するための2次元配列が必要です。

実装のポイント

• メモリ管理: \(N=1000\) の場合、\(1000 \times 1000\) の整数配列を複数保持することになります。Pythonではメモリ消費が大きくなりやすいため、不要になった大きな配列（元のグリッドなど）を del で解放するなどの工夫が有効です。

• スライディングウィンドウの高速化: Pythonにおいてデックを使うとループ回数が多くなり遅くなることがあるため、提示されたコードのように「ブロックごとの累積最大値（pre/suf）」を利用する手法は非常に高速です。

  ソースコード

import sys

def solve():
    # Fast input reading: Read all data from standard input and split into words.
    # This approach is generally efficient for competitive programming in Python.
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N is the size of the grid, K is the size of the square region.
    N = int(input_data[0])
    K = int(input_data[1])
    
    # Build the 2D grid A from the input data.
    # A[i][j] represents the landscape score at row i and column j.
    A = []
    for i in range(N):
        A.append(list(map(int, input_data[2 + i * N : 2 + (i + 1) * N])))
    
    # Free up the memory used by input_data as it is no longer needed.
    del input_data
    
    # Precompute 2D Prefix Sums to find the sum of any KxK region in O(1).
    # S[i][j] will store the sum of all A[r][c] where 0 <= r < i and 0 <= c < j.
    S = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N):
        Ai = A[i]
        Si = S[i]
        Si1 = S[i + 1]
        row_sum = 0
        for j in range(N):
            row_sum += Ai[j]
            Si1[j + 1] = Si[j + 1] + row_sum
    
    # Compute the maximum value in every KxK region using a 2D sliding window.
    # We solve this in O(N^2) by applying 1D sliding window maximum twice.
    # First, calculate the sliding window maximum for each row.
    num_regions = N - K + 1
    B = []
    pre = [0] * N
    suf = [0] * N
    for i in range(N):
        Ai = A[i]
        # Use a block-based algorithm for 1D sliding window maximum.
        # This approach is efficient in Python as it avoids deque overhead.
        for j in range(N):
            if j % K == 0:
                pre[j] = Ai[j]
            else:
                pre[j] = pre[j - 1] if pre[j - 1] > Ai[j] else Ai[j]
        for j in range(N - 1, -1, -1):
            if j == N - 1 or (j + 1) % K == 0:
                suf[j] = Ai[j]
            else:
                suf[j] = suf[j + 1] if suf[j + 1] > Ai[j] else Ai[j]
        
        row_max = [0] * num_regions
        for j in range(num_regions):
            v1 = suf[j]
            v2 = pre[j + K - 1]
            row_max[j] = v1 if v1 > v2 else v2
        B.append(row_max)
    
    # Free up memory used by A as we now have the row-wise maximums in B.
    del A
    
    # Transpose B to process the row-wise maximums column-wise.
    # BT[j] will represent the j-th column of the sliding maximums of A.
    BT = list(zip(*B))
    del B
    
    # Second, calculate the sliding window maximum along the columns of B.
    # C[i][j] will store the maximum landscape score in the KxK region starting at (i, j).
    C = [[0] * num_regions for _ in range(num_regions)]
    for j in range(num_regions):
        col = BT[j]
        for i in range(N):
            if i % K == 0:
                pre[i] = col[i]
            else:
                pre[i] = pre[i - 1] if pre[i - 1] > col[i] else col[i]
        for i in range(N - 1, -1, -1):
            if i == N - 1 or (i + 1) % K == 0:
                suf[i] = col[i]
            else:
                suf[i] = suf[i + 1] if suf[i + 1] > col[i] else col[i]
        
        for i in range(num_regions):
            v1 = suf[i]
            v2 = pre[i + K - 1]
            C[i][j] = v1 if v1 > v2 else v2
            
    # Free up BT as we now have the full 2D region maximums in C.
    del BT
    
    # Calculate the maximum satisfaction Takahashi can obtain.
    # Aoki will always set the maximum value in the chosen region to 0 to minimize satisfaction.
    # Satisfaction = (Sum of KxK region) - (Maximum value in KxK region).
    ans = 0
    for i in range(num_regions):
        SiK = S[i + K]
        Si = S[i]
        Ci = C[i]
        for j in range(num_regions):
            # Sum of the KxK region starting at (i, j) using the prefix sum grid.
            current_sum = SiK[j + K] - Si[j + K] - SiK[j] + Si[j]
            # Satisfaction for this region after Aoki's optimal interference.
            sat = current_sum - Ci[j]
            if sat > ans:
                ans = sat
                
    # Output the result.
    print(ans)

if __name__ == '__main__':
    solve()

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