Codeforces #363 Div1 C. LRU

これ落としてなければHighestだったのにな。
http://codeforces.com/contest/698/problem/C

問題

N個のデータが順に読み込まれる。(同じデータは複数回読み込まれることもある)
その際、最近読み込まれたK個はLRUの要領でキャッシュに残る。

1回の読み込みごとに、各データが選択される確率をP[i]とする。(sum(P)=1)
10^100回読み込みを行った後、各データがキャッシュに残る確率はいくらか。

解法

前から考えていくとLRUの要領でデータの追い出しを考えなければいけない。
逆に後ろ順に見ていって先頭K個まで読み込まれたものがキャッシュに残っていると考えられる。
(同じものは複数回カウントしない)

よってBitDPの要領で解く。
dp(bitmask) := いくつかデータを読んだとき、bitmaskに含まれるものがそれぞれ1回以上読まれた状態となる確率

bitmaskに含まれるデータを再度読んでもLRUの状態は変更されない。
よって、bitmaskに含まれないデータiに対し、以下のように値を更新していく。
(S[bitmask]はbitmask以外のデータの選択確率の総和)
dp(bitmask | (2^i)) += dp(bitmask) * P[i] / S[bitmask]
あとはbitmaskのbitcountがKとなるときが求める状態なので、それらを数え上げればよい。

ただし１つ注意点があり、P[i]＞0である要素がK個未満の場合がある。
この場合K個データが読まれることはないし、そもそもS[bitmask]が0になり0除算になる可能性があるので、その場合は例外処理すること。
というか、P[i]＞0である要素がK個以下の場合、それらは全部キャッシュに載る。

int N,K;
double P[30];
double dp[1<<20];
double R[30];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>P[i];
	
	dp[0]=1;
	for(int mask=0;mask<1<<N;mask++) if(dp[mask]) {
		int ng=0;
		double el=1;
		FOR(i,N) if(mask&(1<<i)) el -= P[i];
		if(el<1e-9 || __builtin_popcount(mask)==K) {
			FOR(i,N) if(mask&(1<<i)) R[i]+=dp[mask];
		}
		else {
			FOR(i,N) if((mask&(1<<i))==0) dp[mask|(1<<i)] += dp[mask] * P[i]/el;
		}
		
	}
	
	FOR(i,N) _P("%.12lf%c",R[i],(i==N-1)?'\n':' ');
}

まとめ

「ただし～～」の部分は自分がやらかして落としたところ。