TopCoder SRM 759 : Div1 Hard EllysTournament

その変形忘れてた…。
https://community.topcoder.com/stat?c=problem_statement&pm=15434

問題

1～N番の人が左から順に1列に並んでおり、各人のレートが与えられる。
ここで、以下の手順を列が1人になるまで繰り返す。

• ある隣接する2人組を、等確率で1つ選ぶ。
• その2人が対戦する。勝率は互いのレートに比例する。
• 敗者は列から除かれる。

K番の人が最後まで勝ち残る確率を求めよ。

解法

まず思いつくのは、以下をDPなりメモ化再帰で埋めることである。
win(L,R,x) := L～R番の人の中でx番が残る確率
win(1,N,K)が解となる。

ただ、これは状態数だけでO(N^3)あり、愚直に求めようとするとO(N^5)ぐらいかかる。
しかしこれは考え方を変えるともう少し状態を減らせる。
x番は自身より左の人の中で1位になり、かつ右の人の中でも1位になればよいので、自身の左側と右側は独立に考えられる。
Lwin(L,R),Rwin(L,R)を、L～R番のうちL,R番が勝ち抜く確率とすると、
win(L,R,x) = Rwin(L,x)*Lwin(x,R)となる。

よってあとはLwin・Rwinの埋め方を考えよう。
例えばLwin(L,R)を考える。L=Rの場合はLwin(L,R)=1である。
そうでないとき、最後L番とx番が争うケースを考えると、最後の直前にL番がk番までの勝者であることを列挙すると

のようになる。Lwin(L,k)*Rwin(k+1,x)は事前に計算しておけば全体をO(N^3)で抑えられる。

double win[505][505];
double memo[505][505][2];
double prob[505][505];

double Win(int L,int R);
double Top(int L,int R,int side) {
	if(L==R) return 1;
	if(memo[L][R][side]>=0) return memo[L][R][side];
	double ret=0;
	int x;
	if(side==0) {
		for(x=L+1;x<=R;x++) ret+=Win(L,x)*prob[L][x]*Top(x,R,0);
	}
	else {
		for(x=L;x<=R-1;x++) ret+=Win(x,R)*prob[R][x]*Top(L,x,1);
	}
	ret/=(R-L);
	return memo[L][R][side]=ret;
}
double Win(int L,int R) {
	if(win[L][R]>=0) return win[L][R];
	double ret=0;
	int x;
	for(x=L;x<R;x++) ret+=Top(L,x,0)*Top(x+1,R,1);
	return win[L][R]=ret;
	
}

class EllysTournament {
	public:
	double getChance(int N, int K, vector <int> R) {
		int x,y;
		FOR(x,N) FOR(y,N) {
			win[x][y]=memo[x][y][0]=memo[x][y][1]=-1;
			prob[x][y]=1.0*R[x]/(R[x]+R[y]);
		}
		K--;
		return Top(0,K,1)*Top(K,N-1,0);
	}
}

まとめ

両端が勝者となるケースだけ考えればいいってのと、(R-L)で割る部分でつまずいた。
前者は前にも同じ手法使ったことあったので、思いつかなかったのは頂けないな…。