8VC Venture Cup 2016 - Elimination Round : D. Jerry's Protest

これはHack出来そうで出来なかった。
http://codeforces.com/contest/626/problem/D

問題

N個のボールを使った２人ゲームを行う。
各ボールは異なる数値A[i]が書かれている。

２人でボールを１個ずつ取り、大きな数値のボールを取った方が勝ちである。
終わったらボールを戻す。

３回ゲームを行ったとき、先２回は先手、３回目は後手が勝つケースのうち、３回合計の数値では後手の方が上回るケースとなる確率を求めよ。

解法

１回ゲームを行うときの組み合わせはO(N^2)通りなので、愚直に３試合分のケースを考えるとO(N^6)かかってしまう。
ここでAの上限が小さいことを活かし、１回ゲームを行ったとき、勝者が数値どれだけの差で勝つかを求めよう。
１回ゲームをやって勝者がxの差で勝つ確率をD(x)とする。

ここから、2回ゲームをやって勝者が合計zの差で2解とも勝つ確率をE(z)とすると、E(z)=sum(D(x)*(Dy)) (x+y=z)でE(z)を求められる。

３試合目、後手がxの差で勝つ場合、先手が先2試合で合計x未満の差で勝っていれば条件を満たすので、が解。
先にEの累積和を計算しておけば、内側のsumはO(1)で計算できる。

int N;
int A[2020];
double D[5050];
double D2[10050];
double S[10050];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(y,N) FOR(x,N) if(A[x]<A[y]) D[A[y]-A[x]]+=2.0/N/(N-1);
	
	FOR(i,5002) if(D[i]) {
		FOR(j,5002-i) if(D[j]) D2[i+j] += D[i]*D[j];
	}
	
	for(i=1;i<=10000;i++) S[i]=S[i-1]+D2[i];
	
	double ret=0;
	FOR(i,5002) if(D[i]) ret += D[i]*S[i-1];
	_P("%.12lf\n",ret);
	
	
}

まとめ

Aが小さいことに気づければ簡単。