SRM 384 Div1 Medium SchoolTrip

問題

何人かが円状に位置しており、一つのボールを互いに当て合うゲームをする。プレイヤーはボールを持っている時、自分以外の人を狙うものとし、i番目のプレイヤーがボールをもっている時に、このプレーヤーが狙った相手に当てることのできる確率はprobability[i]で表される。あるプレイヤーが投げた次のターンは、そのプレイヤーの時計回りに隣のプレイヤーが投げる。ボールを当てられたプレイヤーはゲームから退いていき、プレイヤーが一人になったら終了とする。開始時のプレイヤーを0番目の人としてターン数が最小となるように最適なプレーを行った場合の期待値を求めよ。

やりかた

bitDP。
dp[S][idx][turn]:=（生き残っているプレイヤーのビット集合をS、今ボールをもっている人をidx、現在のターン数をturnとした場合の最小ターン数の期待値）でDP。

プレイヤーが残り一人になるか、ターン数が一定回数以上になったら探索を打ち切るようにする。

以下ソース。

const int MAX = 2000;

double dp[1 << 6][6][MAX];
vector<double> p;

class SchoolTrip {  
public:
  int N;
  //残存プレイヤー集合がstateの時のidxの次のプレイヤーを返す
  int nextturn(int state, int idx){
    for(int i = idx + 1; i < N; i++) if(state >> i & 1) return i;
    for(int i = 0; i < idx; i++) if(state >> i & 1) return i;
  }
  double rec(int S, int idx, int depth){
    if(__builtin_popcount(S) <= 1) return 0.0;//プレイヤーが一人以下になった
    if(depth >= MAX) return 1.00;

    double &ans = dp[S][idx][depth];
    if(ans > 0.0) return ans;
    
    ans = 1e100;
    vector<int> m;//今生き残っているプレイヤー
    for(int i = 0; i < N; i++) 
      if(S >> i & 1) m.push_back(i);
    int L = m.size();

    for(int i = 0; i < L; i++) if(m[i] != idx){
	int nextstate;
	//hit
	nextstate = S ^ (1 << m[i]);//m[i]番目の人に当てた
	double hit = rec(nextstate, nextturn(nextstate, idx), depth + 1) * p[idx];
	//miss
	nextstate = S;//当てられなかった
	double miss = rec(nextstate, nextturn(nextstate, idx), depth + 1) * (1.0 - p[idx]);
	ans = min(ans, 1.0 + hit + miss);
    }
    return ans;
  }
  double duration(vector <int> probability) {
    double ans;
    p.clear();
    N = probability.size();
    for(int i = 0; i < N; i++) p.push_back(probability[i] * 0.01);
    memset(dp, -1, sizeof(dp));
    
    return rec((1 << N) - 1, 0, 0);
  }
};