概要

各地点について、予報気温 \(T_i\) と \(D\) 日間の実際の気温 \(A_{i,j}\) の差の絶対値の合計 \(S_i\) を求め、その最大値を出力する問題です。

考察

地点 \(i\) の予報誤差の合計は、問題文の通り

\(S_i = \sum_{j=1}^{D} |A_{i,j} - T_i|\)

です。

したがって、各地点ごとに次の処理を行えばよいです。

1. 地点 \(i\) の予報気温 \(T_i\) を確認する
2. その地点の \(D\) 日分の実際の気温を読む
3. 各日について \(|A_{i,j} - T_i|\) を足し合わせる
4. これまでの最大値を更新する

たとえば、ある地点の予報気温が \(T_i = 20\) で、実際の気温が \(18, 23, 20\) だった場合、

\(|18 - 20| + |23 - 20| + |20 - 20| = 2 + 3 + 0 = 5\)

となります。

この問題では \(N \times D \leq 10^6\) なので、すべての地点・すべての日についてそのまま計算しても十分高速です。

注意点として、求めるのは「各地点ごとの誤差合計」の最大値です。
日ごとの最大誤差を足したり、すべての誤差の合計を出したりすると誤答になります。

また、実際の気温 \(A_{i,j}\) をすべて保存してから計算する必要はありません。
各地点の行を読み込んだら、その場で合計を計算すれば十分です。

アルゴリズム

以下の手順で処理します。

1. \(N, D\) を入力する
2. 予報気温の配列 \(T\) を入力する
3. 答えを表す変数 ans を \(0\) で初期化する
4. 各地点 \(i\) について、
   • 予報気温 ti = T[i] を取り出す
   • その地点の \(D\) 日分の実際の気温を入力する
   • s = 0 として、各気温 a について abs(a - ti) を加算する
   • ans を max(ans, s) で更新する
5. 最後に ans を出力する

計算量

• 時間計算量: \(O(ND)\)
• 空間計算量: \(O(N)\)

予報気温の配列 \(T\) を保存するために \(O(N)\) のメモリを使います。
実際の気温は各行を読みながら処理するため、全体を保存する必要はありません。

実装のポイント

入力サイズは最大で \(N \times D \leq 10^6\) とある程度大きいため、Python では sys.stdin.buffer.readline を使うと安心です。

また、各地点の実際の気温は次のようにその場で処理できます。

for a in map(int, input().split()):
    s += abs(a - ti)

これにより、\(A\) 全体を二次元配列として持たずに済みます。

ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N, D = map(int, input().split())
    T = list(map(int, input().split()))

    ans = 0
    for i in range(N):
        ti = T[i]
        s = 0
        for a in map(int, input().split()):
            s += abs(a - ti)
        if s > ans:
            ans = s

    print(ans)

if __name__ == "__main__":
    main()

---

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