TopCoder SRM 536 Div1 Medium: RollingDiceDivOne

解法

平均値付近に山が出来る。

コード

import java.util.Arrays;

public class RollingDiceDivOne {

	public long mostLikely(int[] dice) {
		Arrays.sort(dice);

		int N = dice.length;
		long low = 1, high = dice[N - 1];

		for (int i = N - 2; i >= 0; i--) {
			long d = dice[i];

			long toplength = high - (low - 1);
			if (d < toplength) {
				// low+d, (low+1)+(d-1), (low+2)+(d-2), ... が作られる
				// 同時に high+1, (high-1)+2, ... が作られる
				low += d;
				high += 1;
			} else {
				// 幅1-2の頂点になる
				long sum = high + low + d;
				if (sum % 2 == 0) {
					low = sum / 2;
					high = low + 1;
				} else {
					low = (sum + 1) / 2;
					high = low;
				}
			}
		}

		return low;
	}
}