概要

\(N\) 個の気温データ \(A_1, A_2, \ldots, A_N\) が与えられたとき、その平均値 \(\mu\) から最も離れている（\(|A_i - \mu|\) が最大となる）データの番号を出力する問題です。

考察

この問題のポイントは、浮動小数点数の精度誤差をいかに回避するかという点にあります。

素直なアプローチ

まず、平均値 \(\mu\) を計算し、各データとの差の絶対値を求める方法が考えられます。 1. 気温の合計 \(S = \sum A_i\) を求める。 2. 平均値 \(\mu = S / N\) を計算する。 3. 各 \(i\) について \(|A_i - \mu|\) を計算し、最大となる \(i\) を探す。

しかし、プログラミングにおける浮動小数点数（float 型など）は、内部的に 2 進数で表現されているため、割り算の結果に微小な誤差が生じることがあります。特に \(N\) が最大 \(2 \times 10^5\) と大きいため、厳密な比較が必要な場合にこの誤差が原因で誤った判定（WA）をしてしまう可能性があります。

誤差を避ける工夫

比較したい式は \(|A_i - \mu|\) です。これを \(\mu = S / N\) を代入して変形してみましょう。

\[|A_i - \frac{S}{N}| = \frac{|N \cdot A_i - S|}{N}\]

私たちが探したいのは、この値が最大となる \(i\) です。分母の \(N\) はすべての観測地点で共通の正の整数なので、全体の値を最大化することは、分子の \(|N \cdot A_i - S|\) を最大化することと同じです。

この式であれば、登場する値はすべて整数（\(N, A_i, S\)）であるため、計算過程で誤差が発生せず、正確に比較を行うことができます。

アルゴリズム

1. 入力された気温の合計 \(S\) を計算します。
2. 「これまでの最大差」を保持する変数 max_diff を非常に小さい値（または \(-1\)）で初期化します。
3. 各観測地点 \(i = 1, \ldots, N\) について以下を繰り返します。
   • 判定値 \(D = |N \cdot A_i - S|\) を計算します。
   • もし \(D\) が max_diff よりも厳密に大きい場合：
     • max_diff を \(D\) で更新します。
     • 答えとなる番号 ans_idx を \(i\) で更新します。
4. 最終的な ans_idx を出力します。

※「\(D\) が max_diff と等しい」場合に更新しないことで、問題文にある「複数ある場合は番号が最も小さいものを出力する」という条件を自然に満たすことができます。

計算量

• 時間計算量: \(O(N)\)
  • 全データの合計を求めるのに \(O(N)\)、各データを 1 回ずつ確認するのに \(O(N)\) かかるため、全体で \(O(N)\) となります。\(N \le 2 \times 10^5\) なので、十分に高速です。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個のデータをリストに格納するために \(O(N)\) のメモリを使用します。

実装のポイント

• 整数での比較: 前述の通り、abs(n * a[i] - s) を比較対象とすることで、float 型を使わずに判定を行います。

• タイブレーク: 最大値が同じ地点が複数ある場合、最初に現れた（＝番号が小さい）地点を優先するため、比較演算子には > を使い、>= は使いません。

• 入出力の効率: \(N\) が大きいため、Python の場合は sys.stdin.read().split() などを使って一括で入力を読み込むと高速です。

  ソースコード

import sys

def main():
    # 入力をすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Nの取得
    n = int(input_data[0])
    # A_iのリストを取得
    a = list(map(int, input_data[1:]))
    
    # 全観測地点の気温の合計を求める（平均値 mu = s / n）
    s = sum(a)
    
    # |A_i - mu| が最大となる地点を探す
    # |A_i - s/n| を最大化することは、|n * A_i - s| を最大化することと同義
    # これにより浮動小数点数の精度問題を回避できる
    max_diff = -1
    ans_idx = 1
    
    for i in range(n):
        # |n * A_i - s| を計算
        current_diff = abs(n * a[i] - s)
        
        # 最大値を更新した場合のみ番号を更新する
        # （同じ値の場合は番号が小さい方を優先するため、より大きい場合のみ更新）
        if current_diff > max_diff:
            max_diff = current_diff
            ans_idx = i + 1
            
    # 結果を出力
    print(ans_idx)

if __name__ == "__main__":
    main()

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