TopCoder SRM 729 Div2 Hard RareItems

900ptでもいいと思うけど、典型だから800ptなのかな。
https://community.topcoder.com/stat?c=problem_statement&pm=14819

問題

N個のアイテムの１個が当たるくじがある。
各アイテムの登場確率F(i)が与えられる。

全アイテムを1個以上保持するまでにくじを引く回数の期待値を求めよ。

解法

典型問題かな。
現在所有済みのアイテムをbitmaskで管理し、その状態に到達する場合までのくじを引く回数の期待値と、その状態に至る確率を求めていく。
状態遷移する場合は、くじを引く回数の期待値を、到達確率の重みづけで平均を取っていこう。

なお、現在所有しているアイテム群の登場確率の和がpのとき、次に自分が保持してないアイテムが出るまでのくじを引く回数の期待値は1/(1-p)であることは覚えておいて損はない。

int N;
double sum[1<<20];
double prob[1<<20];
double p[20];
double ps[1<<20];

class RareItems {
	public:
	double expectedPurchases(vector <int> frequency) {
		int N=frequency.size();
		int i,S=0,mask;
		FOR(i,N) p[i]=frequency[i], S+=p[i];
		FOR(i,N) p[i]/=S;
		FOR(mask,1<<N) {
			ps[mask]=0;
			prob[mask]=sum[mask]=0;
			FOR(i,N) if(mask&(1<<i)) ps[mask]+=p[i];
		}
		prob[0]=1;
		FOR(mask,(1<<N)-1) {
			double getnew=1.0/(1-ps[mask]);
			double nex=sum[mask]/prob[mask]+getnew;
			FOR(i,N) if((mask&(1<<i))==0) {
				double cp=prob[mask]*(p[i]/(1-ps[mask]));
				sum[mask^(1<<i)] += cp*nex;
				prob[mask^(1<<i)] += cp;
			}
			
		}
		return sum[(1<<N)-1];
	}
}

まとめ

これ系苦手意識があったのですんなり解けて良かった。