概要

\(H \times W\) のグリッドにおいて、ある区画にスポットライトを設置することで、その区画を含む行と列が照らされる。照らされた区画の明るさの合計（照明スコア）を最大化する設置場所を求めよ。

考察

スポットライトを区画 \((r, c)\) に設置したときの照明スコアは、

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

と表されます。これは「\(r\) 行目の合計」と「\(c\) 列目の合計」を足して、重複して加算された \(G_{r,c}\) を引いたものです。

この式を見ると、すべての区画に対して愚直に計算すると、各行の合計と各列の合計を毎回計算する必要があり、全体で \(O(H \cdot W \cdot (H + W))\) の計算量となり、制約が \(H, W \leq 2000\) なので間に合いません（最大で \(8 \times 10^9\) 回程度の計算が必要）。

そこで、事前に各行の合計と各列の合計を前もって計算しておけば、各スポットライト設置位置について \(O(1)\) で照明スコアが求められるようになります。

例えば、以下のような小さな例を見てみましょう：

\[ G = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \]

このとき： - 各行の合計：row_sums = [3, 7] - 各列の合計：col_sums = [4, 6]

スポットライトを \((1,1)\)（0-indexedなら \((0,0)\)）に置くと： $\( \text{score} = 3 + 4 - 1 = 6 \)$

このように、事前に合計を計算しておくことで効率よく求められます。

アルゴリズム

1. 各行の合計を計算し、row_sums 配列に保存する。
2. 各列の合計を計算し、col_sums 配列に保存する。
3. すべての区画 \((i, j)\) に対して、照明スコア row_sums[i] + col_sums[j] - G[i][j] を計算し、最大値を記録する。
4. 最大値を出力する。

計算量

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

※入力の読み込みや合計の計算がボトルネックとなりますが、全体としては線形時間に収まっています。

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用している。

• row_sums と col_sums を事前に計算することで、全探索時の計算を高速化している。

• 明るさの値が負になりうるので、初期値の最大値には十分小さい値（例: float('-inf')）を使用すること。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    H = int(data[0])
    W = int(data[1])
    G = []
    idx = 2
    for _ in range(H):
        row = list(map(int, data[idx:idx+W]))
        idx += W
        G.append(row)
    
    # 各行の合計
    row_sums = [sum(row) for row in G]
    
    # 各列の合計
    col_sums = [0] * W
    for j in range(W):
        for i in range(H):
            col_sums[j] += G[i][j]
    
    max_score = float('-inf')
    for i in range(H):
        for j in range(W):
            score = row_sums[i] + col_sums[j] - G[i][j]
            if score > max_score:
                max_score = score
    
    print(max_score)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。