土下座しながら探索中

主に競技プログラミング

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;
}