概要

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

考察

この問題は、与えられた式をそのまま計算するだけで答えが求まる、いわゆる「全探索（シミュレーション）」で解ける問題です。特別なアルゴリズムや工夫は必要ありません。

各地点 \(i\) に対して、以下の計算を行います。

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

そして \(S_1, S_2, \ldots, S_N\) のうち最大のものを答えとします。

注意すべき点はデータの規模です。 制約より \(N \times D \leq 10^6\) となっており、すべての気温データを読み込んで計算するには最大で \(10^6\) 個の要素を処理する必要があります。要素数自体は問題ないのですが、Python では入力の読み込み方が遅いと TLE（実行時間超過）になることがあります。

たとえば input() を1行ずつ呼び出したり、int() への変換を非効率に行うと、\(10^6\) 個のデータに対しては時間がかかってしまいます。そこで、入力を高速に処理する工夫が重要になります。

具体例で確認してみましょう。地点 \(i\) の予報気温が \(T_i = 10\) で、実際の気温が \([12, 7, 15, 8]\) だったとします。このとき、

\[S_i = |12-10| + |7-10| + |15-10| + |8-10| = 2 + 3 + 5 + 2 = 12\]

となります。これを全地点について計算し、最大値を取るだけです。

アルゴリズム

1. 入力を一括で読み込む。
2. 各地点 \(i\) について、予報気温 \(T_i\) と各日の実際の気温 \(A_{i,j}\) の差の絶対値を合計して \(S_i\) を求める。
3. 計算した \(S_i\) の最大値を更新していく。
4. 最後に最大値を出力する。

絶対値の計算は、差 \(v = A_{i,j} - T_i\) を求めた後、\(v < 0\) なら符号を反転する（\(v = -v\)）ことで求められます。組み込みの abs() 関数を使ってもよいですが、自前で分岐したほうがわずかに高速な場合があります。

計算量

• 時間計算量: \(O(N \times D)\) （制約より最大で \(10^6\)）
• 空間計算量: \(O(N \times D)\) （入力データをすべて保持する場合）

実装のポイント

• 入力の高速化が最重要です。 Python では sys.stdin.buffer.read() で標準入力を一度にすべて読み込み、split() でトークンに分割するのが定石です。これにより、行ごとの読み込みオーバーヘッドを避けられます。

data = sys.stdin.buffer.read().split()

• 読み込んだ data はインデックス idx を進めながら参照していきます。\(N\), \(D\) を読み取った後、予報気温 \(T\)、続いて各地点の気温データを順に処理します。

• 絶対値の計算では、必要な場面でのみ int() 変換を行うことで処理を軽くしています。コードでは int(data[j]) - ti のように、合計を取る直前に整数化しています。

• 最大値は、各地点の \(S_i\) を計算するたびに if s > ans: ans = s で更新していくことで、追加のリストを作らずに求められます。

これらの工夫により、\(10^6\) 規模のデータでも余裕を持って制限時間内に処理できます。

ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    D = int(data[idx]); idx += 1
    T = data[idx:idx+N]
    idx += N
    Ti = [int(x) for x in T]
    
    ans = 0
    for i in range(N):
        ti = Ti[i]
        s = 0
        base = idx
        for j in range(base, base + D):
            v = int(data[j]) - ti
            if v < 0:
                v = -v
            s += v
        idx += D
        if s > ans:
            ans = s
    
    print(ans)

main()

---

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