概要

\(H \times W\) のグリッドが与えられ、各マスにスポットライトを設置したときの十字型に照らされる範囲の明るさの合計（照明スコア）の最大値を求める問題です。

考察

素朴なアプローチとして、各マス \((i, j)\) について照明スコアを直接計算する方法が考えられます。照明スコアは \(i\) 行目の合計と \(j\) 列目の合計から重複してカウントしている \((i, j)\) の値を引いたもの（\(\sum_{k=1}^{W} G_{i,k} + \sum_{k=1}^{H} G_{k,j} - G_{i,j}\)）で計算できます。しかし、各マスについて毎回行と列の合計を計算すると、時間計算量が \(O(HW \times (H + W))\) となり、\(H\) と \(W\) が最大2000の場合、\(2000 \times 2000 \times (2000 + 2000) = 16 \times 10^9\) 回の計算が必要となり、実行時間制限に間に合いません。

そこで、事前に行ごとの合計と列ごとの合計を計算しておくことで、各マスの照明スコアを定数時間で計算できるようにします。これにより、全体の計算量を \(O(HW)\) に抑えることができます。

アルゴリズム

1. 入力を受け取り、グリッドを2次元リストとして保持します。
2. 各行の合計値を格納する配列 row_sums（長さ \(H\)）と、各列の合計値を格納する配列 col_sums（長さ \(W\)）を用意します。
3. グリッドを走査しながら、row_sums[i] に \(i\) 行目の合計を、col_sums[j] に \(j\) 列目の合計を累積します。
4. すべてのマス \((i, j)\) について、照明スコアを row_sums[i] + col_sums[j] - grid[i][j] で計算し、最大値を更新します。
5. 最大値を出力します。

計算量

• 時間計算量: \(O(HW)\)
  • 行と列の合計を計算するための2重ループが \(O(HW)\)
  • 各マスの照明スコアを計算するための2重ループが \(O(HW)\)
• 空間計算量: \(O(HW)\)
  • グリッドの保持に \(O(HW)\)
  • 行合計と列合計の配列に \(O(H + W)\)

実装のポイント

• 行と列の合計を事前計算することで、各マスの照明スコアを定数時間で計算できます。

• 初期値は照明スコアが負になる可能性があるため、十分に小さい値（\(-10^{18}\) など）に設定します。

• 入力値が大きい場合（\(H\) や \(W\) が2000、\(G_{i,j}\) が \(10^9\)）でも整数が扱えるように、Pythonでは整数型の範囲内で処理できます。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    H = int(data[0])
    W = int(data[1])
    grid = []
    index = 2
    for i in range(H):
        row = list(map(int, data[index:index+W]))
        index += W
        grid.append(row)
    
    row_sums = [0] * H
    col_sums = [0] * W
    
    for i in range(H):
        for j in range(W):
            row_sums[i] += grid[i][j]
            col_sums[j] += grid[i][j]
    
    ans = -10**18
    for i in range(H):
        for j in range(W):
            total = row_sums[i] + col_sums[j] - grid[i][j]
            if total > ans:
                ans = total
                
    print(ans)

if __name__ == "__main__":
    main()

この解説は deepseekv3.1 によって生成されました。