概要

各マス \((r,c)\) にスポットライトを置いたときの「行の総和 + 列の総和 − 自分」を高速に計算し、最大値を求める問題です。

考察

スポットライトを \((r,c)\) に置いたときの照明スコアは
\(\sum_{j=1}^{W} G_{r,j} + \sum_{i=1}^{H} G_{i,c} - G_{r,c}\)
です。ここで重要なのは、

• \(\sum_{j=1}^{W} G_{r,j}\) は「行 \(r\) の総和」
• \(\sum_{i=1}^{H} G_{i,c}\) は「列 \(c\) の総和」
• \(G_{r,c}\) は行と列で2回足してしまうので1回引く

という分解ができる点です。

素朴解が遅い理由

各マス \((r,c)\) について、行方向に \(W\) 個・列方向に \(H\) 個を毎回足すと、 - 1マスあたり \(O(H+W)\) - 全マスで \(O(HW(H+W))\)

となります。制約は \(H,W \le 2000\) なので最悪 \(HW=4\times 10^6\)、これにさらに \((H+W)\approx 4000\) を掛けると現実的な時間では間に合いません。

解決策

先に - 各行の総和 row[r] - 各列の総和 col[c]

を \(O(HW)\) で前計算しておけば、任意の \((r,c)\) のスコアは

\(score(r,c)=row[r]+col[c]-G_{r,c}\)

で \(O(1)\) で求まります。あとは全マスを走査して最大を取るだけです。

アルゴリズム

1. 入力を読みながら、配列 row と col にそれぞれ行和・列和を蓄積する。
   同時に後で \(G_{r,c}\) を参照できるよう、全要素を配列 a（1次元）に保存する。
2. 全マス \((r,c)\) について
   • \(val = row[r] + col[c] - G_{r,c}\) を計算し、最大値を更新する。
3. 最大値を出力する。

（例）
行和が row[r]=10、列和が col[c]=7、交点が G[r][c]=3 なら
\(10+7-3=14\) が照明スコアになります。

計算量

• 時間計算量: \(O(HW)\)
• 空間計算量: \(O(HW + H + W)\)

実装のポイント

• 64bit整数が必要: 値は最大で \(2000 \times 10^9 = 2\times 10^{12}\) 規模の和になりうるため、32bit では溢れます。Python の int は大丈夫ですが、保存用配列は 64bit を想定します。

• メモリ対策: \(HW\) が最大 \(4\times 10^6\) なので、Python の通常の list に int を詰めるとメモリが大きくなりがちです。コードでは array('q')（64bit符号付き）で G を保持し、メモリを抑えています。

• 高速入力: 要素数が最大 400万個あるため、sys.stdin.buffer.read() で一括読み込みして整数に変換する自前パーサで高速化しています。

  ソースコード

import sys
from array import array

def int_stream():
    data = sys.stdin.buffer.read()
    n = len(data)
    i = 0
    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            return
        sign = 1
        if data[i] == 45:  # '-'
            sign = -1
            i += 1
        num = 0
        while i < n and data[i] > 32:
            num = num * 10 + (data[i] - 48)
            i += 1
        yield sign * num

it = int_stream()
H = next(it)
W = next(it)

row = [0] * H
col = [0] * W

N = H * W
a = array('q', [0]) * N

for r in range(H):
    base = r * W
    s = 0
    for c in range(W):
        v = next(it)
        a[base + c] = v
        s += v
        col[c] += v
    row[r] = s

col_local = col
a_local = a
ans = -10**30

for r in range(H):
    base = r * W
    rs = row[r]
    for c in range(W):
        val = rs + col_local[c] - a_local[base + c]
        if val > ans:
            ans = val

print(ans)

---

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