beet's soil

競プロのことなど

TCO 2018 R3B med TestProctoring

うく

概要

1秒に1回試験が行われている。
 N (1 \le N \le 20) 人の生徒がいて、各生徒は  p_i / q_i の確率で試験に合格する。
全員が合格するまでにかかる時間の期待値を求めよ

解法

制約以外はよくある期待値DP  O(3^N) は自明 前計算してDP

 double expectedTime(vector <int> P, vector <int> Q) {
    int n=P.size();
    vector<double> p(n);
    for(int i=0;i<n;i++) p[i]=(double)P[i]/Q[i];
    int s=1<<n;

    vector<double> sc(s,1),fa(s,1);
    for(int b=0;b<s;b++){
      for(int i=0;i<n;i++){
	if((~b>>i)&1) continue;
	sc[b]*=p[i];
	fa[b]*=1.0-p[i];
      }
    }
    
    vector<double> dp(s,0);
    for(int b=1;b<s;b++){
      int nb=b;
      while(nb){
	nb=(nb-1)&b;
	int k=b^nb;
	dp[b]+=(dp[nb]+1.0)*sc[k]*fa[nb];
      }
      dp[b]+=fa[b];
      dp[b]/=1.0-fa[b];
    }
    return dp[s-1];
  }

まあ  N=20 だと全然間に合わない

まとめて遷移することを考える 
立っているbitのうち一つ消すみたいな遷移にまとめるっぽい雰囲気を感じる
上の  sc[k] の部分が厄介だが式変形すると sc[k] = sc[b] / sc[nb] であるから先に割っておいて後から戻せることがわかる

複数段をまたいでしまうと重複して数えてしまう
部分集合の出現回数を考えると高さごとに決まっていることがわかる
コンテスト中は  O(N 2^N) にこだわってしまったが  O(N^2 2^N) が間に合うので愚直に各段ごとに試せばよい

  double expectedTime(vector <int> P, vector <int> Q) {
    int n=P.size();
    vector<double> p(n);
    for(int i=0;i<n;i++) p[i]=(double)P[i]/Q[i];
    int s=1<<n;

    vector<double> sc(s,1),fa(s,1);
    for(int b=0;b<s;b++){
      for(int i=0;i<n;i++){
	if((~b>>i)&1) continue;
	sc[b]*=p[i];
	fa[b]*=1.0-p[i];
      }
    }
    vector<double> po(n+1,1);
    for(int i=1;i<=n;i++) po[i]=po[i-1]*i;
    vector<double> dp(s,0);
    vector<vector<double> > sm(n+1,vector<double>(s,0));
    sm[0][0]+=(dp[0]+1.0)*fa[0]/sc[0];
    for(int b=1;b<s;b++){
      int cnt=0;
      for(int i=0;i<n;i++){
	if((~b>>i)&1) continue;
	int nb=b^(1<<i);
	for(int j=0;j<=n;j++) sm[j][b]+=sm[j][nb];
	cnt++;
      }
      
      for(int j=cnt;j>=0;j--)
	dp[b]+=sm[j][b]*sc[b]/po[cnt-j];
      
      dp[b]+=fa[b];
      dp[b]/=1.0-fa[b];
      sm[cnt][b]+=(dp[b]+1)*fa[b]/sc[b];
    }
    return dp[s-1];
  }
反省

なんで一時間あって詰められないんでしょうか
まあこのタイプの係数の調整方法は知らなかったので勉強になった