hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

TopCoder SRM 729 Div2 Hard: RareItems

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

 N 個のアイテムが出るくじがある。 i 番目のアイテムが出る頻度は  f_i である (すなわち、 i 番目が出る確率は  \frac{f_i}{\sum_{k=1}^{N} f_k} )。  N 個すべてのアイテムを出すまでに必要な、くじを引く回数の期待値を求めよ。

解説

このスライド の pp.36-40 を参照してください (雑)

確率と期待値について結構頑張ってまとめたスライドなのでほかも参考になれば嬉しいです。

ちなみに、 RareItems の類題として、 AtCoderソーシャルゲーム があります (くじが複数あるだけでほぼ同じ問題)

ソースコード

class RareItems {
    public:
    double expectedPurchases(vector<int> frequency) {
        int N = frequency.size();
        // すべてのアイテムの頻度の和 (全事象)
        int sum = accumulate(frequency.begin(), frequency.end(), 0);

        // dp[S] := 既に得たアイテムの集合が S であるとき、
        //          S からフルコンプするまでに必要な回数の期待値
        vector<double> dp(1<<N, 0.0);
        for(int bit=(1<<N)-1; bit>=0; bit--) {
            // 既に得ているアイテムの頻度和
            int already_get = 0;
            for(int i=0; i<N; i++) {
                if(bit >> i & 1) already_get += frequency[i];
            }

            // 未取得のアイテムの頻度和
            int sum_part = sum - already_get;

            if(sum_part) {
                // 未取得のアイテムが出るまで引く回数の期待値
                double exp_num = 1.0 * sum / sum_part;

                // 未取得のアイテムを何かひとつ引く → 集合を更新
                for(int i=0; i<N; i++) {
                    if(!(bit >> i & 1)) {
                        // 未取得のアイテムの集合が決定しているとき、
                        // i 番目のアイテムを引く確率 (条件付き確率)
                        double prob = 1.0 * frequency[i] / sum_part;
                        int nbit = bit | (1 << i);
                        dp[bit] += (dp[nbit] + exp_num) * prob;
                    }
                }
            }
        }
        return dp[0];
    }
};