Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-03-13SRM494、SRM498など(DIV1)

SRM494 第二問(500pt) AlternatingLane

|  SRM494 第二問(500pt) AlternatingLane - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM494 第二問(500pt) AlternatingLane - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=11309

各木の間のBeauty期待値を計算していけばいい、ということに気づきさえすれば簡単。

あとは 100,000 * 100,000 でintの範囲を超えてしまうため、longで計算することに気をつける。


public class AlternatingLane {
	public long sumexternal(int f, int c, int d) {
		long cthigh = d - c + 1;
		long sumhigh = (d + c) * cthigh / 2;
		long ct = 0;
		ct += sumhigh;
		ct = Math.abs(sumhigh - f * cthigh);
		return ct;
	}

	public long suminternal(int f, int c, int d) {
		long ct = 0;
		ct += (long)(f - c) * (long)(f - c + 1) / 2;
		ct += (long)(d - f) * (long)(d - f + 1) / 2;
		return ct;
	}

	public double expectedBeauty(int[] low, int[] high) {
		int len = low.length;
		if (len == 1) {
			return 0;
		}

		double res = 0.0d;
		for (int i = 0 ; i < len - 1 ; i++) {
			long ct = 0;
			for (int f = low[i] ; f <= Math.min(low[i+1] - 1, high[i]) ; f++) {
				ct += sumexternal(f, low[i+1], high[i+1]);
			}
			for (int f = Math.max(low[i+1], low[i]) ; f <= Math.min(high[i+1], high[i]) ; f++) {
				ct += suminternal(f, low[i+1], high[i+1]);
			}
			for (int f = Math.max(high[i+1] + 1, low[i]) ; f <= high[i] ; f++) {
				ct += sumexternal(f, low[i+1], high[i+1]);
			}
			res += (double)ct / (double)((long)(high[i+1] - low[i+1] + 1) * (long)(high[i] - low[i] + 1));
			System.out.println(res + "/");
		}

		return res;
	}
}