Codeforces ECR #013 : E. Another Sith Tournament

これは本番思いつかなかった。
http://codeforces.com/contest/678/problem/E

問題

N人の人で大会を行う。
先頭の２人が試合し、負けた方が脱落して列から抜け、最後１人残った人が優勝という形式で争う。
２人x,yが試合すると、確率P(x,y)でxが勝利する。

N人の並び順を任意に選択できるとき、1番の人が優勝できる確率を最大化し、その確率を答えよ。

解法

前から順に考えていくのは難しいので以下を考える。

dp(mask,x) := 残ってる人がbitmaskで、列の最前列にいる人がxの時、1番の人が優勝する確率
dp(1,0)=1とし、dp((2^N)-1,x)の最大値を求めればよい。

dp(mask,x)を考える際、その直前にxとyが試合した場合dp(mask,x) = dp(mask^(2^x),y) * P(y,x) + dp(mask^(2^y),x) * P(x,y)となりうる。
あとはyを探索してdp(mask,x)を最大化すればよい。

int N;
double P[20][20];
double dp[1<<18][18];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,N) FOR(x,N) cin>>P[y][x];
	if(N==1) return _P("1.0\n");
	
	dp[1][0]=1;
	for(int mask=2;mask<1<<N;mask++) {
		FOR(x,N) FOR(y,N) if(x!=y && ((mask>>x)&1) && ((mask>>y)&1))
			dp[mask][x] = max(dp[mask][x], dp[mask^(1<<x)][y]*P[y][x] + dp[mask^(1<<y)][x]*P[x][y]);
	}
	
	_P("%.12lf\n",*max_element(dp[(1<<N)-1],dp[(1<<N)-1]+N));
	
}

まとめ

こういう逆から考えるの、さらっと思いつかないことが多いなぁ。