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

}