Codeforces 163 C. Conveyor

問題

長さ片面のlのベルトコンベアがある。
コンベア上にチョコレートがn個あり、それぞれの位置はa[i]である。

ベルトコンベアはv1で動いている。
片方の端から、ベルトコンベアの移動と同じ向きに、速度v2で走る。
走っている間にチョコレートの上にきたら、チョコレートを取る。
スタートと同時にチョコは取れるが、ゴールと同時にチョコを取ることはできない。

移動を開始するとき、ベルトコンベアの位置はランダムであるとき、
チョコを取れる個数ごとの確率を出力せよ。

制約条件

n≦10^5
l, v1, v2≦10^9

方針

チョコを取れる個数が変化する点を覚えておく。
個数の変化の累積和が、その区間から走りはじめたときのチョコの獲得個数になるので、区間の長さから確率を計算すればいい。

ソースコード

double a[200000], p[100001];

void run()
{
	int n, l, v1, v2;
	cin >> n >> l >> v1 >> v2;
	rep(i, n) cin >> a[i];
	sort(a, a + n);
	rep(i, n) a[i+n] = a[i] + 2 * l;
	double d = v2 * 1.0 * l / (v1 + v2);
	map<double, int> ps;
	
	rep(i, n) ps[a[i]]--;
	rep(i, 2*n) if(0 <= a[i] - d && a[i] - d < 2 * l) ps[a[i] - d]++;
	
	if(!ps.count(0)) ps[0] = 0;
	if(!ps.count(2 * l)) ps[2 * l] = 0;
	
	int cnt = lower_bound(a, a + 2 * n, d) - a;
	fr(i, ps){
		cnt += i->second;
		map<double, int>::iterator it = i;
		it++;
		if(it == ps.end()) break;
		p[cnt] += (it->first - i->first) / (2 * l);
	}
	
	rep(i, n + 1) printf("%.20f\n", p[i]);
}