概要

この問題は、各地点における \(D\) 日間の「予報気温と実際の気温の差の絶対値の合計（予報誤差の合計）」を計算し、その中で最も大きい値を求める問題です。

考察

各地点 \(i\) の予報誤差の合計 \(S_i\) は、他の地点の気温データとは独立に計算することができます。

具体的には、地点 \(i\) について以下のように計算します。 1. 地点 \(i\) の予報気温 \(T_i\) と、 \(j\) 日目の実際の気温 \(A_{i,j}\) の差の絶対値 \(|A_{i,j} - T_i|\) を求める。 2. これを \(1\) 日目から \(D\) 日目まで足し合わせる。

制約に注目すると、地点数 \(N\) と日数 \(D\) の積 \(N \times D\) は最大で \(10^6\) です。 各地点の各日のデータに対して行う操作は「引き算」「絶対値の取得」「足し算」のシンプルな計算のみであるため、すべての地点と日数の組み合わせ（ \(N \times D\) 通り）を愚直にループで走査しても、計算回数は最大で \(10^6\) 回程度に収まります。これは一般的なプログラミング言語の制限時間（通常2.0秒）に対して十分に高速に動作します。

したがって、各地点について誤差の合計 \(S_i\) を順番に計算し、その中の最大値を記録していくアプローチで正解を得ることができます。

アルゴリズム

1. 入力データをすべて読み込みます。
2. 最大の予報誤差の合計を保持する変数 max_S を \(0\) で初期化します。
3. 地点 \(i\) （ \(0\) から \(N-1\) まで）について、以下の処理を繰り返します：
   • 地点 \(i\) の予報誤差の合計 \(S\) を \(0\) で初期化する。
   • 地点 \(i\) の \(D\) 日間の実際の気温データ \(A_{i, 1}, A_{i, 2}, \ldots, A_{i, D}\) を取得する。
   • 各日の実際の気温 \(x\) について、 \(S\) に \(|x - T_i|\) を加算する。
   • \(S\) が max_S より大きければ、 max_S を \(S\) で更新する。
4. 最終的な max_S の値を出力します。

計算量

• 時間計算量: \(O(N \times D)\) 各地点 \(N\) について、それぞれ \(D\) 日分の気温データを走査するため、ループの総回転数は \(N \times D\) 回となります。制約より \(N \times D \le 10^6\) であるため、実行時間制限に余裕で間に合います。

• 空間計算量: \(O(N \times D)\) 入力されるすべての気温データをメモリ上に保持するため、入力サイズに比例したメモリを使用します。

実装のポイント

• 高速な入力処理: Pythonで入力の要素数が多くなる場合（ \(10^6\) 個程度）、 input() を何度も呼び出すと入出力処理がボトルネックになり実行時間制限（TLE）に引っかかる可能性があります。sys.stdin.read().split() を使用して入力を一括で取得し、整数に変換することで、高速に処理を始めることができます。

• 1次元配列のスライスによる効率化: 2次元配列を厳密に構築する代わりに、1次元に平坦化された配列 A_flat から、各地点 \(i\) に対応する範囲をスライス A_flat[offset : offset + D] で切り出すことで、シンプルかつ高速に各地点のデータを取得しています。

  ソースコード

import sys


def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    all_data = [int(x) for x in input_data]
    N = all_data[0]
    D = all_data[1]
    T = all_data[2 : 2 + N]
    A_flat = all_data[2 + N :]

    max_S = 0
    for i in range(N):
        t = T[i]
        offset = i * D
        row = A_flat[offset : offset + D]
        S = 0
        for x in row:
            S += abs(x - t)
        if S > max_S:
            max_S = S

    print(max_S)


if __name__ == "__main__":
    main()

この解説は gemini-3.5-flash-high によって生成されました。