AtCoder Regular ContestのC問題、全完しました。

問題としてはそう難しくはないのだろうとは思う。 しかし私の場合は解説を見てもなおかなり苦戦した。

C - ソーシャルゲーム

問題

お金を払ってくじを引ける。くじを引くとアイドルがひとり手に入る。くじは複数種類ある。 くじ毎に金額とアイドルの出現確率が与えられるので、最適な戦略を取ったときの、全アイドルの入手に必要な金額の期待値を求めよ。

解法

後ろからbit-dp。dp[入手済みアイドルの集合] = コンプリートまでに必要な金額の期待値。$O(m2^n)$。

前からやろうとすると、そもそも期待値にならないのでだめ。

久しぶりに期待値なんて概念を使ったので少し混乱したので、その部分だけメモしておく。 くじ$i$を引いたとき、確率$q$で入手済みのアイドルを入手できるとすると、 未入手のアイドルを引くまでにくじを引く回数の期待値は、 \(\sum_{n = 1}^{\infty} q^{n-1}n = \frac{1}{1-q} \cdot \sum_{n = 1}^{\infty} q^n = \frac{1}{(1 - q)^2}\)となる。 これ以降の詳しい式はまあ適当にやればでてくる。

実装

#include <iostream>
#include <vector>
#include <cmath>
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat(i,n) repeat_from(i,0,n)
#define repeat_from_reverse(i,m,n) for (int i = (n)-1; (i) >= (m); --(i))
#define repeat_reverse(i,n) repeat_from_reverse(i,0,n)
using namespace std;
int main() {
    int n, m; cin >> n >> m;
    vector<int> c(m);
    vector<int> cost(m);
    vector<vector<int> > idol(m);
    vector<vector<int> > p(m);
    repeat (i,m) {
        cin >> c[i] >> cost[i];
        idol[i].resize(c[i]);
        p[i].resize(c[i]);
        repeat (j,c[i]) {
            cin >> idol[i][j] >> p[i][j];
            -- idol[i][j];
        }
    }
    vector<double> dp(1 << n, INFINITY);
    dp[(1 << n) - 1] = 0;
    repeat_reverse (s, 1 << n) {
        repeat (i, m) {
            double acc = 0;
            int q = 0; // duplicated
            repeat (j, c[i]) {
                int t = s | (1 << idol[i][j]);
                if (s == t) q += p[i][j];
            }
            if (q == 100) continue;
            repeat (j, c[i]) {
                int t = s | (1 << idol[i][j]);
                if (s != t) acc += cost[i] * (p[i][j]/100.0 / pow(1 - q/100.0, 2))
                                    + (p[i][j]/100.0 / (1 - q/100.0)) * dp[t];
            }
            dp[s] = min(dp[s], acc);
        }
    }
    printf("%.12lf\n", dp[0]);
    return 0;
}