Thumbnail [第5回 ドワンゴからの挑戦状 予選 A]

atcoder.jp

①長さ n の数列が与えられる。この数列の各項には 0,1,2,3,4......n-1 の番号が付けられている
②数列の平均値に最も近い項の、その番号を出力せよ。

解説に「a の平均値を X とします。X は整数となるとは限りませんが、NX は平均値の定義より必ず整数となります」とあります。これは、長さ n の数列の平均値を求めるには数列の総和を n で割る必要があり、このとき総和が n の倍数であれば、平均値が少数にならない、ということみたいです。

平均値が少数にならないということは、それと各項を比較するときに整数同士で比較でき、誤差が発生しないということになります。なるほど、誤差を生まないようにするための、こんな方法があったんですね。今回の問題では、平均値を通常通り少数で求めて、それと各項を比較しても誤差で弾かれることはないみたいですが、もっとレベルの高い問題を解くときのためにこの方法は覚えておきたいです。

//dwacon5th-prelims-a
 
import java.util.*;
 
class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		int n = sc.nextInt();
		int[] ar = new int[n];
		int sum = 0;
		for (int i=0; i<n; i++) {
			int temp = sc.nextInt();
			ar[i] = temp;
			sum += temp;
		}
		int avg = sum / n;
		
		int min = Integer.MAX_VALUE;
		int ans = -1;
		for (int i=0; i<n; i++) {
			if (Math.abs(ar[i]-avg) < min) {
				min = Math.min(min, Math.abs(ar[i]-avg));
				ans = i;
			}
		}
		
		System.out.println(ans);
		
	}
}

入力を n 倍してから配列に格納することで、全ての項が n の倍数になり、したがって総和も n の倍数になります。n の倍数である総和を n で割って平均値を出すので、平均値が少数になることはありません。