Croc Champ 2013 - Final : A. Morning run

Croc FinalはOnlineで参加。Aをhackされた上に自分はhackミスしてマイナススコア。
その直後にA・Cは自力で解答、Bは周りの解答を見ながら復習。
http://codeforces.com/contest/309/problem/A

問題

長さLの円形トラックをN人の人間が速度1で走る。
各人が時計回りで回るか反時計まわりで走るかは確率は半々である。
N人の初期位置が与えられたとき、T時間走った場合に人同士がぶつかる回数の期待値を求めよ。

解法

T>=Lの場合、T/L周するので逆向きに走る人は必ず2*T/L回ずつぶつかる。
T%L >= L/2の場合、さらにお互い半周するので、逆向きに走る人はもう1回ぶつかる。

あとはT = T % (L/2)して考える。
各人がぶつかるのは、反時計まわりに走る場合は初期位置から反時計回り2*Tまでの位置にいるひとが時計回りに走る場合と、時計回りに走る場合に初期位置から2*Tまでの位置にいる人が反時計回りに走ってくる場合。
上記の数はlower_boundやupper_boundを使えばO(log N)で求められる。

最後にぶつかると思われる両者が想定通りの方向に走る確率1/4を掛けて答え。
合わせてO(N log N)。

ll N;
ll L,T;
ll A[1000002];

void solve() {
	int f,r,i,j,k,l, x,y,ma,num,nt;
	ll tot = 0;

	cin>>N>>L>>T;
	FOR(i,N) cin>>A[i];
	for(i=N-1;i>=0;i--) A[i]*=2;
	L*=2;
	T*=2;
	for(i=N-1;i>=0;i--) A[i]-=A[0];
	if(T>=L) {
		tot = 2*N*(N-1)*(T/L);
		T%=L;
	}
	if(T*2>=L) {
		tot += N*(N-1);
		T-=L/2;
	}

	FOR(i,N) {
		ll LF=A[i]-2*T;
		ll RF=A[i]+2*T;

		if(LF<0) {
			ll* p=lower_bound(A,A+N,L+LF);
			tot += A+N-p;
			//_P("L %d %lld %lld\n",i,tot,L+LF);
		}
		ll* p=upper_bound(A,A+N,RF);
		tot += (p-1)-(A+i);
		//_P("R %d %lld %lld\n",i,tot,RF);
	}

	double res = tot/4.0;
	_P("%.12lf\n",res);

	return;
}

まとめ

問題のためにひねくりだした問題よりも、こういう現実にありそうな？シチュエーションの問題は結構好き。