概要

この問題は、各 \(K \times K\) 区域について

• 区域内の総和
• 区域内の最大値

を求め、\(\text{総和} - \text{最大値}\) の最大を探す問題です。
総和と最大値をそれぞれ「スライドしながら」計算することで、全体を \(O(N^2)\) で解けます。

考察

まず、青木君が何をするかを整理します。

区域内の 1 マスを選んでその値を \(0\) にするので、区域の合計は「選んだマスの値」だけ減ります。
青木君は満足度を最小化したいので、最も大きい値のマスを選ぶのが最適です。

したがって、ある \(K \times K\) 区域の満足度は

\[ \text{満足度} = \text{区域内の総和} - \text{区域内の最大値} \]

になります。

---

素朴な方法が遅い理由

すべての \(K \times K\) 区域を調べると、個数は

\[ (N-K+1)^2 \]

個あります。

各区域について \(K^2\) 個のマスを見て総和や最大値を求めると、全体は

\[ O((N-K+1)^2 K^2) \]

となり、最悪で \(O(N^4)\) 級です。
\(N \le 1000\) では到底間に合いません。

---

重要な気づき

2 次元の \(K \times K\) 区域を、横方向→縦方向の 2 段階で処理します。

1. まず各行ごとに、幅 \(K\) の区間を考える

各行 \(i\) について、各開始列 \(c\) に対して

• row_sums[i][c] = 行 \(i\) の列 \(c\) から \(c+K-1\) までの和
• row_maxs[i][c] = 行 \(i\) の列 \(c\) から \(c+K-1\) までの最大値

を求めます。

これは 1 行上の「長さ \(K\) の区間」の問題なので、

• 和 → 通常のスライド
• 最大値 → 単調キュー

で \(O(N)\) で求められます。

---

2. 次に縦方向に \(K\) 行まとめる

列の開始位置 \(c\) を固定すると、\(K \times K\) 区域の総和は

\[ \sum_{i=r}^{r+K-1} \text{row\_sums}[i][c] \]

です。
つまり「row_sums[*][c] を縦に長さ \(K\) で足したもの」です。

また、その区域の最大値は

\[ \max_{i=r}^{r+K-1} \text{row\_maxs}[i][c] \]

です。

なぜなら、各行の横幅 \(K\) の区間の最大値を取り、その中でさらに最大を取れば、ちょうど \(K \times K\) 全体の最大値になるからです。

これも縦方向のスライドで処理できます。

• 総和 → 縦にスライドしながら加減算
• 最大値 → 単調キュー

これで各列開始位置ごとに \(O(N)\)、全体で \(O(N^2)\) です。

---

具体例

たとえば \(K=2\) のとき、ある列開始位置 \(c\) を固定すると、

• 各行について「横 2 マスの和」と「横 2 マスの最大値」を先に作る
• その後、連続する 2 行をまとめる

ことで、各 \(2 \times 2\) 区域について

• 総和 = 行ごとの横 2 マス和の合計
• 最大値 = 行ごとの横 2 マス最大値の最大

がすぐに分かります。

アルゴリズム

\(M = N-K+1\) とします。

1. 各行について、幅 \(K\) の区間の和と最大値を求める

各行 \(i\) について、長さ \(M\) の配列を作ります。

• row_sums[i][c]
• row_maxs[i][c]

求め方は以下です。

• 和は、右端を 1 つ進めるごとに
  • 新しく入る値を足す
  • 範囲から外れる値を引く
• 最大値は、単調減少になるように deque を保つことで求める

---

2. 各列開始位置 \(c\) ごとに、縦方向へスライドする

列開始位置 \(c\) を固定し、上から順に行を見ます。

総和

cur_sum を

\[ \text{現在の } K \text{ 行分の } row\_sums[*][c] \text{ の合計} \]

として管理します。

最大値

row_maxs[i][c] に対して、縦方向の長さ \(K\) の区間最大を単調キューで管理します。

すると、行 \(i\) が現在の下端のとき、\(i \ge K-1\) なら

• 区域の総和 = cur_sum
• 区域の最大値 = row_maxs[dq[0]][c]

なので

\[ \text{満足度} = \text{cur\_sum} - \text{row\_maxs[dq[0]][c]} \]

を計算して最大値を更新します。

---

3. 最終的な最大値を出力する

計算量

• 時間計算量: \(O(N^2)\)
• 空間計算量: \(O(N(N-K+1)) = O(N^2)\)

実装のポイント

• 単調キューでは、最大値を取りたいので

  • 後ろから「今入れる値以下」の要素を取り除く
  • 先頭が現在の範囲外なら取り除く という形にします。

• 値の合計は最大で $\( 10^9 \times 10^6 = 10^{15} \)$ 程度になるので、Python 以外の言語では long long など 64bit 整数が必要です。

• この実装では元の \(N \times N\) 配列全体を保存せず、各行を読んだその場で横方向の情報を作っています。これにより実装がすっきりしています。

  ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())
    M = N - K + 1

    row_sums = [None] * N
    row_maxs = [None] * N

    for i in range(N):
        row = list(map(int, input().split()))
        sums = [0] * M
        mxs = [0] * M

        dq = deque()
        s = 0
        for j, x in enumerate(row):
            s += x
            if j >= K:
                s -= row[j - K]

            while dq and row[dq[-1]] <= x:
                dq.pop()
            dq.append(j)
            if dq[0] <= j - K:
                dq.popleft()

            if j >= K - 1:
                idx = j - K + 1
                sums[idx] = s
                mxs[idx] = row[dq[0]]

        row_sums[i] = sums
        row_maxs[i] = mxs

    ans = 0

    for c in range(M):
        dq = deque()
        cur_sum = 0

        for i in range(N):
            cur_sum += row_sums[i][c]
            v = row_maxs[i][c]

            while dq and row_maxs[dq[-1]][c] <= v:
                dq.pop()
            dq.append(i)
            if dq[0] <= i - K:
                dq.popleft()

            if i >= K:
                cur_sum -= row_sums[i - K][c]

            if i >= K - 1:
                cand = cur_sum - row_maxs[dq[0]][c]
                if cand > ans:
                    ans = cand

    print(ans)

if __name__ == "__main__":
    main()

---

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