Codeforces Round #363 (Div. 1) C. LRU

競プロ Codeforces

問題文

http://codeforces.com/contest/698/problem/C

解法

10^100なので実質無限大の時間がたったと考えて良い．
正規マルコフだし，十分大きな時間が経過したあとは定常状態に落ち着く．
この時，過渡状態にいる確率はほぼ0で，キャッシュは（できるかぎり）満杯になっていることになる．
以降，出来る限り満杯になるときのキャッシュサイズを K と再定義する．

つまり，最後から見て直近 K 種類のビデオがなにかわかればいい．
このように後ろから考えることによって，途中でLRUの機能によってキャッシュから取り除く操作を考える必要がなくなる．

さて，現在の瞬間にみるビデオは，過去に見たビデオに影響されない．
したがって，
「最後からみて（相異なる）直近 i 種類のビデオが v1, v2, ..., vi である確率」
は
「最初からみて（相異なる）直近 i 種類のビデオが v1, v2, ..., vi である確率」
と等しい．
これは，bitDPで求めることができる．
直近みたビデオの集合をビットで管理することにして，それを S で表す．
つまり，dp[S] := 最初から考えて，初めて popcount(S) 種類になったときそれが S である確率 とする．

S -> S | (1 << i) の遷移では
dp[S | (1 << i)] += dp[S] * p[i] / (1 - q)
となる．ただし，q は S に含まれるビデオの確率の総和である．
なぜなら，この遷移で問題になるのは，S に含まれないビデオの中で，次に見たものは一体何か？ということだからである．
各時刻で見るビデオは過去の状態に無関係だから，S 以外で次にビデオ i を見る確率は単純に p[i] / (1 - q) として良い．

あとは，popcount(S) == K となっているものを考えて，和を取ればOK．

・補足
K をできるかぎり満杯のキャッシュサイズとしたのは，完全に満杯にならない場合があるからである．
それは，n 種類の中に確率0のビデオがある場合である．

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    int cnt = 0;
    vector<double> p(n);
    for(int i = 0; i < n; ++i) {
        cin >> p[i];
        cnt += p[i] == 0;
    }
    k = min(k, n - cnt);

    vector<double> dp(1 << n);
    dp[0] = 1;
    for(int S = 0; S < (1 << n); ++S) {
        if(__builtin_popcount(S) >= k) {
            continue;
        }
        double q = 0;
        for(int i = 0; i < n; ++i) {
            if((S >> i) & 1) {
                q += p[i];
            }
        }
        for(int i = 0; i < n; ++i) {
            if((S >> i) & 1) {
                continue;
            }
            dp[S | (1 << i)] += dp[S] * p[i] / (1 - q);
        }
    }

    vector<double> res(n);
    for(int S = 0; S < (1 << n); ++S) {
        if(__builtin_popcount(S) == k) {
            for(int i = 0; i < n; ++i) {
                if((S >> i) & 1) {
                    res[i] += dp[S];
                }
            }
        }
    }

    for(int i = 0; i < n; ++i) {
        cout << fixed << setprecision(10) << res[i] << " \n"[i == n - 1] << flush;
    }
}

感想

後ろからやる～っていうのは頻出でよく見るんだけど，普通に遷移がわからなかった．
最近簡単な数学ができなくなっていて反省．