Codeforces Round #363 (Div. 2) E. LRU

問題

Problem - E - Codeforces
N個のデータと容量Kのキャッシュがある．キャッシュのアルゴリズムにLRUが使われていて，無限のクエリが飛んできたとき，最後のキャッシュの状態にそれぞれのデータが含まれる確率はいくつか．

解法

簡単に言うと，キャッシュの最後の状態をすべて挙げてそれが起こる確率をbitDPで計算する．最後から逆戻りして考える．
集合Sの要素がすでにキャッシュに入っているときの，Sに含まれない要素eがキャッシュに入る確率はp[e]/(Sに含まれない要素の確率の和)になる．よって
に含まれない要素の確率の和)
という漸化式が得られる．
コンテスト中は，Sがキャッシュに入っているときでもSの要素を追加しようとすることがあるのでその確率をどう考えればいいか悩んでいたが，上のようにS以外の要素についてだけ考えられるようにすることでうまくできる．また，(Sに含まれない要素の確率の和)は0になることもあり得るので，それにも対処する必要がある．

ソースコード

#include <iostream>
#include <iomanip>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)

double p[20], ans[20];
double dp[1<<20];

int main(void) {
    int i, j, n, k;
    cin >> n >> k;
    REP (i,n) cin >> p[i];

    int zero = 0;
    REP (i,n) if (p[i] < 1e-9) zero++;
    if (zero >= n - k) {
        REP (i,n) ans[i] = p[i] >= 1e-9;
    }
    else {
        dp[0] = 1;
        REP (i,1<<n) {
            if (__builtin_popcount(i) >= k) continue;
            double total = 0;
            REP (j,n) if (!(i&1<<j)) total += p[j];
            REP (j,n) if (!(i&1<<j)) {
                dp[i|1<<j] += dp[i] * p[j] / total;
            }
        }
        REP (i,1<<n) if (__builtin_popcount(i) == k) REP (j,n) if (i&1<<j) {
            ans[j] += dp[i];
        }
    }

    REP (i,n) cout << fixed << setprecision(8) << ans[i] << (i < n-1 ? ' ' : '\n');
    return 0;
}