TopCoder SRM 526.5 Div1 Medium: MagicBlizzard
解法
まずrangeでソートする.ソートすると,前のrangeは後ろのrangeで完全に覆われるので,前のamountはそのまま全て後ろに引き継がれる.
コード
import java.util.ArrayList; import java.util.Collections; public class MagicBlizzard { public double expectation(int[] range, int[] amount) { int N = range.length; double ans = 0; ArrayList<Blizzard> blizzards = new ArrayList<>(N); for (int i = 0; i < N; i++) { blizzards.add(new Blizzard(range[i], amount[i])); } Collections.sort(blizzards); long all = 0; for (int i = 0; i < N; i++) { double r = blizzards.get(i).range; double area = (2 * r + 1) * (2 * r + 1); for (int j = 0; j < blizzards.get(i).amount; j++) { double cell = all / area;// 1セルあたりの雪球の平均値 double diff = (cell + 1) * (cell + 1) - cell * cell; ans += diff; all++; } } return ans; } } class Blizzard implements Comparable<Blizzard> { int range, amount; public Blizzard(int range, int amount) { this.range = range; this.amount = amount; } @Override public int compareTo(Blizzard o) { return this.range - o.range; } }