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

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

問題

n 個のビデオがあり、i 番目のビデオが参照される確率は p[i] である。ビデオは参照されるたびにサイズ K のキャッシュに保存される。すでにキャッシュに K 個のデータが保存されていた場合は、最後に参照された時間が最も遠いものを破棄する。

10¹⁰⁰ 回の操作後にビデオ i がキャッシュされている確率を求めよ。

解法

一番最後に参照された K 種類が何なのかが分かればいい。 逆から考えることで、K 種類集まるまでガチャを回す問題と見ることができる。

• dp[ キャッシュされたビデオの集合 ] := この状態になる確率

既にあるアイテムの集合を S として、次に引いたガチャがダブる確率を q とすると、S→(S|1<<i) と遷移する確率は p[i]/(1-q) になる（10¹⁰⁰ は実質∞なので）。これを使って DP を更新していけばいい。

確率 0 のものがあると、必ずしも K 個集まるとは限らないということに注意。

言われてみれば納得という感じの問題。