概要

全地点の平均気温 \(\mu\) からの距離 \(|A_i-\mu|\) が最大となる観測地点を求め、同率なら最小の番号を出力します。

考察

平均値は \(\mu=\dfrac{\sum_{j=1}^{N}A_j}{N}\) なので、各地点で \(|A_i-\mu|\) を計算して最大を探せばよいです。

ただし素朴に \(\mu\) を 浮動小数（double） で計算して比較すると、誤差の影響で - 本当は同じ距離なのに大小がズレる
- 本当は等しいはずの値が微妙に違って比較が壊れる
といった WA の原因になり得ます（特に「同率なら最小番号」という条件があるため危険です）。

そこで、分数を分数のまま比較する発想を使います。 [ |A_i-\mu| = \left|A_i-\frac{S}{N}\right| = \left|\frac{A_iN-S}{N}\right| ] （ただし \(S=\sum A_j\)）

ここで、\(N\) は全ての \(i\) で共通の正の定数なので、大小比較は分母 \(N\) を無視して [ |A_iN-S| ] だけを比べれば十分です。これなら整数計算だけで正確に比較できます。

例：\(N=3, A=[0,1,2]\) のとき \(S=3, \mu=1\)
- \(i=1\): \(|0\cdot 3-3|=3\)（距離 \(=1\)） - \(i=2\): \(|1\cdot 3-3|=0\) - \(i=3\): \(|2\cdot 3-3|=3\)（距離 \(=1\)）
最大は同率で \(i=1,3\) なので最小番号の \(1\) を出力します。

アルゴリズム

1. 入力を受け取り、配列 \(A\) の総和 \(S\) を計算する。
2. 各 \(i=1..N\) について値 [ v_i = |A_iN-S| ] を計算する。
3. \(v_i\) が最大となる \(i\) を保持する（同率なら更新しないことで最小番号が残る）。
4. 最終的な \(i\) を出力する。

計算量

• 時間計算量: \(O(N)\)（総和計算＋1回走査）
• 空間計算量: \(O(N)\)（配列 \(A\) を保持するため）

実装のポイント

• 浮動小数を使わず、比較対象を \(|A_iN-S|\) に変換して 整数のみで比較すると安全です。

• 同率時に「番号が最小」を満たすには、更新条件を > のみにして == のとき更新しないようにします（先に見つかった小さい番号が残る）。

• \(N \le 2\times 10^5\) なので、Python では sys.stdin.buffer.read() を使うと入力が高速です。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    N = int(data[0])
    A = list(map(int, data[1:1+N]))
    S = sum(A)

    best_idx = 1
    best_val = -1
    for i, a in enumerate(A, 1):
        v = abs(a * N - S)
        if v > best_val:
            best_val = v
            best_idx = i
    print(best_idx)

if __name__ == "__main__":
    main()

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