概要

\(H \times W\) のグリッドにおいて、ある区画 \((r, c)\) を選んだとき、\(r\) 行目全体と \(c\) 列目全体の明るさの合計（交差点は1回だけカウント）を最大化する問題です。

考察

照明スコアの式を理解する

区画 \((r, c)\) にスポットライトを設置したときの照明スコアは次の式で表されます：

\[\text{score}(r, c) = \sum_{j=1}^{W} G_{r,j} + \sum_{i=1}^{H} G_{i,c} - G_{r,c}\]

これは「\(r\) 行目の合計」＋「\(c\) 列目の合計」−「交差点 \((r,c)\) の値（重複分を引く）」です。

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

もし各 \((r, c)\) について行の合計と列の合計を毎回計算すると、1回あたり \(O(H + W)\) かかり、全体で \(O(H \times W \times (H + W))\) となります。\(H, W \leq 2000\) のとき、これは約 \(4000 \times 4 \times 10^6 = 1.6 \times 10^{10}\) 回程度の計算となりTLEします。

解決策：前計算

照明スコアの式をよく見ると、\(\sum_{j=1}^{W} G_{r,j}\) は行 \(r\) にのみ依存し、\(\sum_{i=1}^{H} G_{i,c}\) は列 \(c\) にのみ依存します。つまり：

• 各行の合計 \(\text{row\_sum}[i]\) を事前に計算
• 各列の合計 \(\text{col\_sum}[j]\) を事前に計算

しておけば、各 \((r, c)\) の照明スコアは \(O(1)\) で求められます。

アルゴリズム

1. 入力を読み込み、グリッド \(G\) を格納する。
2. 行ごとの合計 \(\text{row\_sum}[i] = \sum_{j=1}^{W} G_{i,j}\) を計算する。
3. 列ごとの合計 \(\text{col\_sum}[j] = \sum_{i=1}^{H} G_{i,j}\) を計算する。
4. すべての \((i, j)\) について \(\text{score} = \text{row\_sum}[i] + \text{col\_sum}[j] - G_{i][j}\) を計算し、その最大値を求める。

具体例

例えば以下の \(2 \times 3\) のグリッドを考えます：

 1  2  3
 4  5  6

• \(\text{row\_sum} = [6, 15]\)
• \(\text{col\_sum} = [5, 7, 9]\)

区画 \((2, 3)\) を選ぶと： $\(\text{score} = 15 + 9 - 6 = 18\)$

これは 2行目（4+5+6=15）と 3列目（3+6=9）の合計から交差点の6を1回引いた値です。

計算量

• 時間計算量: \(O(H \times W)\)（前計算に \(O(H \times W)\)、全探索に \(O(H \times W)\)）
• 空間計算量: \(O(H \times W)\)（グリッド格納に必要。行・列の合計配列は \(O(H + W)\)）

実装のポイント

• オーバーフローに注意: \(G_{i,j}\) の絶対値が最大 \(10^9\) で、行や列の長さが最大 2000 なので、合計は最大 \(2 \times 10^{12}\) 程度になります。Python では整数のオーバーフローがないため問題ありませんが、C++ などでは long long を使う必要があります。

• 高速な入力: Python では sys.stdin.buffer.read() でまとめて読み込むことで、入力のボトルネックを軽減しています。

• 初期値: 答えの初期値を -float('inf') にすることで、すべての値が負の場合にも正しく動作します。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    H = int(input_data[idx]); idx += 1
    W = int(input_data[idx]); idx += 1
    
    row_sum = [0] * H
    col_sum = [0] * W
    G = []
    
    for i in range(H):
        row = []
        s = 0
        for j in range(W):
            v = int(input_data[idx]); idx += 1
            row.append(v)
            s += v
            col_sum[j] += v
        row_sum[i] = s
        G.append(row)
    
    ans = -float('inf')
    for i in range(H):
        for j in range(W):
            score = row_sum[i] + col_sum[j] - G[i][j]
            if score > ans:
                ans = score
    
    print(ans)

main()

---

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