概要

観測地点ごとの気温データから平均値との差の絶対値が最も大きい地点の番号を求め、複数ある場合は最も小さい番号を出力する問題です。

考察

この問題では、まず全ての観測地点の気温の平均値 \(\mu\) を計算する必要があります。平均値は全気温の合計を観測地点数 \(N\) で割ることで求められます。その後、各観測地点について \(|A_i - \mu|\) を計算し、この値が最大となる地点を探します。

重要な点は、平均値からの距離が同じ場合に「番号が最も小さい」ものを選択するという条件です。また、気温の値が整数ですが、平均値は小数になる可能性があるため、浮動小数点数の計算が必要になります。

アルゴリズム

1. 入力から観測地点数 \(N\) と気温のリスト \(A\) を読み込む
2. 全気温の合計を計算し、平均値 \(\mu = \frac{\text{sum}(A)}{N}\) を求める
3. 各観測地点についてループ処理を行い：
   • \(|A_i - \mu|\) を計算
   • 現在の最大差よりも大きければ、最大差と結果のインデックスを更新
   • 現在の最大差と等しく、かつインデックスが現在の結果より小さければ、結果のインデックスを更新
4. 最終的に得られたインデックス（0-indexed）に1を加えて出力（1-indexedに変換）

計算量

• 時間計算量: \(O(N)\)
  • 気温の合計計算に \(O(N)\)
  • 各観測地点の差の計算と比較に \(O(N)\)
• 空間計算量: \(O(N)\)
  • 気温データを格納するための配列

実装のポイント

• 平均値の計算で浮動小数点数を使用する必要がある

• インデックスの比較時に、同じ差の値の場合のみ番号の大小を比較する

• 0-indexedから1-indexedへの変換を忘れない（結果に+1する）

• 初期値として最大差を-1、結果インデックスを-1に設定し、必ず最初の要素で更新されるようにする

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    A = list(map(int, data[1:1+n]))
    
    total = sum(A)
    mu = total / n
    
    max_diff = -1
    result_index = -1
    
    for i in range(n):
        diff = abs(A[i] - mu)
        if diff > max_diff:
            max_diff = diff
            result_index = i
        elif diff == max_diff:
            if i < result_index:
                result_index = i
                
    print(result_index + 1)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。