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; } }