ARC016 C問題：ソーシャルゲーム

問題. ソーシャルゲーム

$N$ 種類のカードと $M$ 種類のくじがある． $i$ 番目のくじを引くのにかかる費用は $c_i$ で，くじを引いたときに得られるカードの集合を $D_i \subseteq \{1, 2, \ldots, N\}$ とする．また， $i$ 番目のくじを引いて $j \in D_i$ 番目のカードが当たる確率を $p_{i, j}$ とする．
最適な戦略でくじを引いて全種類のカードをコンプリートするまでにかかる費用の期待値を答えよ．

制約： $1 \le N \le 10$ ，　 $1 \le M \le 4$ ，　 $1 \le c_i \le 3,000$

解法．期待値＋動的計画法

カードの集合を $C = \{1, 2, \ldots, N\}$ ，くじの集合を $L = \{1, 2, \ldots, M\}$ とする．最適な戦略でくじを引いていくときに，どのくじを選択すればよいかの判断材料は今までに得られたカードの情報のみであることが分かる．そこで，任意のカードの部分集合 $S \subseteq C$ に対して確率変数 $X_S$ を「現在，カード $S$ が手元にある状態からコンプリートするまでにかかる最小費用」と定義する．このとき初期状態は $E [X_{C} ] = 0$ であり，求める答えは $E[X_\emptyset$ ] である．この期待値を動的計画法で求めることを考える．

$E[X_\emptyset$ ] を求めるために，さらに確率変数を定義する．任意の $S \subseteq C$ と $i \in L$ に対して確率変数 $Y_{S, i}$ を「現在，カード $S$ が手元にある状態から，次に $i$ 番目のくじを引くと決めたときにコンプリートするまでにかかる最小費用」と定義する．また，任意の $i \in L$ と $j \in C$ に対して $A_{i, j}$ を「くじ $i$ を選択してカード $j$ を引く事象」とする．ここで，任意の $S \subsetneq C$ に対して，

　 $E[X_S] = \min_{i \in M} \{E [Y_{S, i} ]\} \qquad (☆)$

となる．右辺の各引数をさらに展開すると

　 $E [Y_{S, i} ] = \sum_{j \in D_i} E[ Y_{S, i} \mid A_{i, j} ] \cdot \text{Pr}(A_{i, j})$
　　　　　 $= \sum_{j \in D_i \cap S} E[ Y_{S, i} \mid A_{i, j} ] \cdot \text{Pr} (A_{i, j}) + \sum_{j \in D_i \setminus S} E [ Y_{S, i} \mid A_{i, j}] \cdot \text{Pr} (A_{i, j})$
　　　　　 $= \sum_{j \in D_i \cap S} E[ c_i + X_S ] \cdot p_{i, j} + \sum_{j \in D_i \setminus S} E [ c_i + X_{S \cup \{j\}} ] \cdot p_{i, j}$
　　　　　 $= \sum_{j \in D_i \cap S} (c_i + E[X_S ]) \cdot p_{i, j} + \sum_{j \in D_i \setminus S} (c_i + E [X_{S \cup \{j\}} ]) \cdot p_{i, j}$
　　　　　 $= E[X_S ] \sum_{j \in D_i \cap S} p_{i, j} + c_{i} + \sum_{j \in D_i \setminus S} E[ X_{S \cup \{j\} }] \cdot p_{i, j}$

となる．1番目の等号は全期待値の法則を用いて，5番目の等号は $\sum_{j \in D_i \cap S} p_{i, j} + \sum_{j \in D_i \setminus S} p_{i, j} = 1$ を用いている．さらに（☆）から $E[X_S ] \le E[Y_{S, i} ]$ となるので，

　 $E[X_S] \le E[X_S ] \sum_{j \in D_i \cap S} p_{i, j} + c_{i} + \sum_{j \in D_i \setminus S} E[ X_{S \cup \{j\} }] \cdot p_{i, j}$

である．これを整理すると

　 $E[X_S] \le \frac{c_i + \sum_{j \in D_i \setminus S} E[X_{S \cup \{j\}} ] \cdot p_{i, j}}{1 - \sum_{j \in D_i \cap S} p_{i, j}}$

となる．上式は定義から等号を与えるくじ番号が存在するので，任意のくじに対して計算した右辺の値の最小値を $E[X_S]$ に代入すればよい．さらに， $|S| \le 10$ なので bitDP で計算しても間に合う．注意として $S$ は降順に遷移を行い，上式の右辺の分母が 0 になる場合，すなわち $i$ 番目くじを引いても新たにカードを得られない場合は除外して計算する必要がある．
問題の入力データ $p_{i, j}$ は百分率で与えられるので下のソースコードでは上式を少し変形している．

計算時間： $O(M 2^N)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cout << setprecision(8) << setiosflags(ios::fixed);

    struct Card { int id, p; };
    struct Lottery {
        int cost;
        vector<Card> cards;
    };

    int N, M;
    cin >> N >> M;

    vector<Lottery> lots(M);
    for (auto &l : lots) {
        int C;
        cin >> C >> l.cost;
        l.cards.resize(C);
        for (auto &c : l.cards) {
            cin >> c.id >> c.p;
            --c.id;
        }
    }

    const int SIZE = 1 << N;
    vector<double> dp(SIZE, DBL_MAX);
    dp[SIZE - 1] = 0.0;

    for (int s = SIZE - 2; 0 <= s; --s) {
        for (const auto l_i : lots) {
            double nu = l_i.cost;
            int de = 0;

            for (const auto &card : l_i.cards) {
                if (s >> card.id & 1) de += card.p;
                else nu += dp[s | (1 << card.id)] * 0.01 * card.p;
            }

            if (de != 100) {
                double c_i = (100.0 * nu) / (100.0 - de);
                dp[s] = min(dp[s], c_i);
            }
        }
    }

    cout << dp[0] << endl;

    return 0;
}