Typical DP contest C トーナメント

2013-08-31

02:19 |

2^K 人がトーナメント対戦する。人 i, j が対戦して i が勝つ確率が式で与えられる。各人が優勝する確率を求める。
1≦K≦10

わからないので工夫とかなしで何を計算すべきか考えてみる
dp[k][i] ... k回戦が終わった段階で人iが勝ち残ってる確率と置いてみる. (実際は2面だけ用意した
各対戦で戦う可能性のある人すべてのパターンで確率を計算してdp[k+1]に足してく
決勝は 512x512 →おー間に合うじゃん
accepted

double f(double EP, double EQ) {
	return 1.0 / (1 + pow(10, (EQ-EP)/400));
}

int main() {
	//ios::sync_with_stdio(false);
	ll K;
	while(cin>>K) {
		VI E(1<<K);
		REP(i, 1<<K) cin>>E[i];
		
		vector<double> p(1<<K, 1), np(1<<K);
		REP(round, K) {
			int size = 1<<round;
			int games = (1<<K)/size/2;
//			cout<<"round: "<<size<<" "<<games<<endl;
			REP(game, games) {
				int asidx = game*size*2;
				int bsidx = game*size*2+size;
				REP(ai, size) {
					REP(bi, size) {
						double pawin = f(E[asidx+ai], E[bsidx+bi]);
						np[asidx+ai] += p[asidx+ai]*p[bsidx+bi]*pawin;
						np[bsidx+bi] += p[asidx+ai]*p[bsidx+bi]*(1-pawin);
					}
				}
			}
//			cout<<"np: "<<np<<endl;
			p = np;
			np = vector<double>(1<<K);
		}
		REP(i, 1<<K) cout<<p[i]<<endl;
	}
	
	return 0;
}