TopCoder SRM 384 Div1 Medium SchoolTrip

問題

1番からn番の生徒n人が輪になって次のようなゲームをする。

• 最初は1番の人のターン。ターンは時計まわりに進む
• ターンの人は、だれか一人を選んでボールを投げる。
• それが命中する確率はprobability[i]%
• 命中したら、当たった人は輪から抜ける

これを最後の一人になるまで繰り返す。

生徒たちはゲームを嫌々やっているので（本文中にそう書いてある。わろす）、
終了までにかかるターンの期待値が最小になるように、ボールを投げる相手を選ぶ。

終了までにかかるターンの期待値を求めよ。

制約条件

n≦60
10≦probability[i]≦100

方針

dp[i][pos][mask]を、iターン経過したときに、
pos番目の人のターンで、maskの人が残っているときにかかるターンの期待値とする。

dp[i][pos][mask]は、
jを1からnとして
dp[i+1][pos+1][mask^j]*p[pos]+dp[i+1][pos+1][mask]*(1-p[pos])+1
の最小値になるため、
これを更新していくようなDPができる。

これを収束するまで（1000回程度でよいらしい）まわす。
ボールを自分にぶつけるのを許してもサンプルが通ってしまう……

ソースコード

typdef long double ld;
const int MX=10000;
int n;
ld p[6],dp[2][6][1<<6];

class SchoolTrip {
  public:
  double duration(vector <int> probability) {
    n=probability.size();
    rep(i,n)p[i]=probability[i]/100.0;
    
    int cur=0,next=1;
    rep(j,6)rep(k,1<<6)dp[0][j][k]=0;
    
    rep(t,MX){
      rep(c,n)rep(mask,1<<n){
        if(__builtin_popcount(mask)<2){
          dp[next][c][mask]=dp[cur][c][mask];
          continue;
        }
        ld &res=dp[next][c][mask];
        int pos=c;
        for(;!(mask&1<<pos);pos=(pos+1)%n);
        
        res=INF;
        rep(i,n)if(i!=pos&&(mask&1<<i)){
          res=min(res,dp[cur][(pos+1)%n][mask^1<<i]*p[pos]
            +dp[cur][(pos+1)%n][mask]*(1-p[pos])+1);
        }
      }
      swap(cur,next);
    }
    return dp[cur][0][(1<<n)-1];
  }
};