TopCoder SRM 470 Div1 Medium DrawingLines

問題

上側にn個の点1,2,...,nがあり、下側にn個の点1,2,...,nがある。
上側の点startDot[i]と下側の点startDot[i]が線で結ばれている。

まだ線で結ばれていない上側の点と下側の点を、ランダムに選び線で結ぶ。
全ての点を線で結んだあと、出来ている線の交点の数の期待値を求めよ。

制約条件

n≦10000
startDotとendDotの要素数は等しい
startDotの要素数≦50

方針

上側のi番目の点から下へ引かれる線と上側のj番目の点から下へ引かれる線が交わる期待値を求める。
それぞれを独立に求めた後で、期待値を足し合わせれば、全ての交点の期待値の数が求められる。

i番目の点から引かれる線とj番目の点から引かれる線が交点をもつ確率は、
元々それぞれの点から最初から線が引かれている場合、そうでない場合に分けて求めることができる。

ソースコード

int p[10001],cnt[10001];

class DrawingLines {
	public:
	double countLineCrossings(int n, vector <int> startDot, vector <int> endDot) 
	{
		memset(p,-1,sizeof(p));
		rep(i,n)cnt[i]=1;
		rep(i,startDot.size()){
			p[startDot[i]-1]=endDot[i]-1;
			cnt[endDot[i]-1]=0;
		}
		rep(i,n)cnt[i+1]+=cnt[i];
		
		double ans=0;
		rep(j,n)rep(i,j){
			if(p[i]<0&&p[j]<0)ans+=0.5;
			else if(p[i]<0)ans+=(cnt[n-1]-cnt[p[j]])*1.0/cnt[n-1];
			else if(p[j]<0)ans+=cnt[p[i]]*1.0/cnt[n-1];
			else ans+=p[i]<p[j]?0:1;
		}
		return ans;
	}
};