概要

各地点について予報誤差の合計を計算し、その最大値を求める問題です。定義に従って素直に計算すれば解けます。

考察

この問題では、\(N\) 個の地点それぞれについて \(D\) 日間の予報誤差の合計 \(S_i\) を求め、その最大値を出力します。

• 地点 \(i\) の予報気温は毎日同じ値 \(T_i\) である
• 予報誤差は \(|A_{i,j} - T_i|\)（絶対値）で定義される
• 各地点について \(D\) 日分の誤差を合計し、全地点の中で最大のものを求める

特別なアルゴリズムは不要で、定義通りに計算すれば十分です。制約として \(N \times D \leq 10^6\) が保証されているため、全データを走査しても計算量は問題ありません。

具体例

例えば \(N=2, D=3\)、予報気温が \(T = [10, 20]\)、実際の気温が： - 地点1: \([12, 8, 15]\) - 地点2: \([25, 18, 20]\)

の場合： - \(S_1 = |12-10| + |8-10| + |15-10| = 2 + 2 + 5 = 9\) - \(S_2 = |25-20| + |18-20| + |20-20| = 5 + 2 + 0 = 7\)

最大値は \(\max(9, 7) = 9\) となります。

アルゴリズム

1. \(N\) と \(D\) を読み込む
2. 予報気温 \(T_1, T_2, \ldots, T_N\) を読み込む
3. 各地点 \(i\) について：
   • 実際の気温 \(A_{i,1}, \ldots, A_{i,D}\) を読み込む
   • \(S_i = \sum_{j=1}^{D} |A_{i,j} - T_i|\) を計算する
4. \(S_1, S_2, \ldots, S_N\) の最大値を出力する

計算量

• 時間計算量: \(O(N \times D)\)（各地点の各日について誤差を1回ずつ計算）
• 空間計算量: \(O(D)\)（1地点分の実際の気温を保持するだけで十分）

\(N \times D \leq 10^6\) の制約があるため、十分高速に動作します。

実装のポイント

• 全地点の気温データを一度にメモリに読み込む必要はなく、1地点ずつ処理すればメモリを節約できます。コードでは for i in range(N) のループ内で各地点のデータを読み込み、即座に \(S_i\) を計算しています。

• ans 変数を0で初期化し、各 \(S_i\) を計算するたびに max で更新することで、最終的に最大値が得られます（\(S_i \geq 0\) は絶対値の和なので常に成り立つため、初期値0で問題ありません）。

  ソースコード

N, D = map(int, input().split())
T = list(map(int, input().split()))
ans = 0
for i in range(N):
    A = list(map(int, input().split()))
    s = sum(abs(a - T[i]) for a in A)
    ans = max(ans, s)
print(ans)

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