AtCoder Regular Contest 016 C - ソーシャルゲーム

問題

 アイドルN人を集めるためにM種類のガシャを回すことを考える。それぞれのガシャは一回に一人のアイドルを排出する。各ガシャについて確率分布と回すためにかかる金額が与えられるとき、全てのアイドルを入手することについて最適な戦略の下での必要な金額の期待値を求めよ。

解法

 bitDPで後ろから求める。クリエイティヴなヴログに詳しく書かれていて、自分もこれを読んで理解できたので参照のこと。

反省

 1時間35分でAC。部分点を順番に取りに行ったが、40点のところで根本的に自分の考えていた期待値の式が間違っていたことに気づく。40点を得るのにかかったのが48分ほどで、そこからようやくコンプガチャ形式の部分点について考え始めたがわからず、開始から1時間ほど経ったので解説などを見る。しかし解説スライドはよくわからなくて、上に貼った記事を読んでやっと理解できた。かなり難しい気がする。

 確率系のDPは本当に苦手でさっぱりできない。基本的にDPができない。

 遷移できるかどうか、そして遷移できる中での確率、という二段構えで考えるのが肝心なところだったようだ。正直DPでやるという考えにすらたどり着いていないので、まだこういう考え方の習得には時間がかかりそう。

 しかしN \le 2という部分点問題がかなりヒントになっているはずで、それを解いた時にDP的な考え方をしているにも関わらず次で拡張していけないのが本当にひどい。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll N, M;

int main() {
    cin >> N >> M;
    vector<ll> C(M);
    vector<double> cost(M);
    vector<vector<ll>> idol(M);
    vector<vector<double>> p(M);
    for (ll i = 0; i < M; i++) {
        cin >> C[i] >> cost[i];
        idol[i].resize(C[i]);
        p[i].resize(C[i]);
        for (ll j = 0; j < C[i]; j++) {
            cin >> idol[i][j] >> p[i][j];
            idol[i][j]--;
            p[i][j] /= 100;
        }
    }

    //まだ持ってないところにビットが立つ
    vector<double> dp(1 << N, INT_MAX);

    //全て持っている状態を初期化
    dp[0] = 0.0;

    for (ll i = 1; i < (1 << N); i++) {
        for (ll j = 0; j < M; j++) {
            //持ってないカードを引ける確率を求める
            double success = 0.0;
            for (ll k = 0; k < C[j]; k++) {
                if (i & (1 << idol[j][k])) {
                    success += p[j][k];
                }
            }
            if (success == 0.0) {
                continue;
            }

            //持ってないカードを引ける = 遷移
            //まず遷移する期待値で初期化
            double expect = cost[j] / success;
            for (ll k = 0; k < C[j]; k++) {
                if (i & (1 << idol[j][k])) {
                    //遷移するという条件下での条件付確率×遷移先からかかる期待値
                    expect += (p[j][k] / success) * dp[i ^ (1 << idol[j][k])];
                }
            }

            dp[i] = min(dp[i], expect);
        }
    }

    printf("%.10f\n", dp[(1 << N) - 1]);
}