UVa 11181 : Probability|Given

UVa演習 2014/7/14 (月) 問1

問題リンク : http://uva.onlinejudge.org/external/111/11181.html

問題概要：
N人の人がショッピングにいく
人i ( 1 <= i <= N ) が何かを購入する確率を p[i] とする
N人中ちょうどr人が何かを購入する時、人iが何かを購入する確率を求めよ

制約：
1 <= N <= 20
0 <= r <= N
0.1 < p[i] < 1

解法:
Nが２０人しかいないので、全探索する
20C10がそんなに大きくない
人iが何かを購入する確率は
(N人中ちょうどr人が何かを購入するとき、人iがr人の中に含まれている確率の総和) / (N人中ちょうどr人が何かを購入する確率)

コード:

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

int n,r;
double p[30],sum[30],total;

bool dfs(int cur,int cnt,double dp,int bitmask){
  if( cnt >= r ) {
    rep(i,n) if( !( (bitmask>>i) & 1 ) ) dp *= (1-p[i]);
    total += dp;
    rep(i,n) if( (bitmask>>i) & 1 ) sum[i] += dp;
    return true;
  }
  REP(i,cur,n) dfs(i+1,cnt+1,dp*p[i],bitmask|(1<<i));
  return false;
}

int main(){
  int CNT = 1;
  while( cin >> n >> r, n|r ) {
    rep(i,n) {
      cin >> p[i];
      sum[i] = 0;
    }
    total = 0;
    dfs(0,0,1,0);
    printf("Case %d:\n",CNT++);
    rep(i,n) printf("%.6f\n",sum[i]/total);
  }
  return 0;
}