Typical DP Contest C - トーナメント
問題リンク : C: トーナメント - Typical DP Contest | AtCoder
解法 :
DP全然思い浮かばなかったので愚直に計算した
他の人のコード見て勉強します
コード:
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) using namespace std; double R[1200],dp[2][1200]; int K; inline double calc(double P,double Q) { return 1.0 / ( 1.0 + pow(10.0,(Q-P)/400.0)); } void dfs(int cur_K) { if( cur_K <= 1 ) { for(int i=0;i<(1<<K);i+=2) { dp[cur_K&1][i] = calc(R[i],R[i+1]); dp[cur_K&1][i+1] = calc(R[i+1],R[i]); } return; } dfs(cur_K-1); int phase = cur_K&1; rep(i,(1<<K)) dp[phase][i] = 0; rep(winner,(1<<K)) { int size = (1<<cur_K); int pre_size = (1<<(cur_K-1)); for(int i=0;i<(1<<K);i+=size) { if( i <= winner && winner < i+size ) { int range_L=-1,range_R=-1; for(int j=i;j<i+size;j+=pre_size){ if( j <= winner && winner < j+pre_size ) { range_L = j, range_R = j+pre_size; break; } } REP(j,i,i+size) { if( range_L <= j && j < range_R ) continue; dp[phase][winner] += dp[!phase][winner] * dp[!phase][j] * calc(winner[R],R[j]); } break; } } } } void compute(int K) { dfs(K); rep(i,(1<<K)) printf("%.10f\n",dp[K&1][i]); } int main() { cin >> K; rep(i,(1<<K)) cin >> R[i]; compute(K); return 0; }