2017-10-27

ARC016 - C ソーシャルゲーム

#競プロ

解説

C - ソーシャルゲーム

問題概要

商品が n 種類、くじが m 種類あります。くじを一度引くのにお金がかかります。くじからは、ある確率である商品が手に入ります。

最善を尽くしたとき、全ての商品を集める金額の期待値を求めてください。

考えたこと

期待値についてはこちら期待値と条件付確率 - math314のブログ 1 、問題文についてはこちら ARC016-C「ソーシャルゲーム」の記事が非常に参考になります。

こちら期待値と条件付確率 - math314のブログの記事で例として挙げられているコイントスの期待値についてです。頂点の値が、連続で表が出た回数を示しています。青矢印が表が出たことを、橙矢印が裏が出たことを表しています。期待値はこのように状態の遷移から式を立てることができます。

単純なくじで、期待値を求める式を立ててみます。 E は、その状態から全ての商品を集めるためにくじを引く回数を表しています。

頂点の値は、商品の入手を bit で表しています。 00 の状態からそれぞれ 10, 01 の状態へ遷移し、最後は 11 となります。 11 は全て揃った状態でありこれ以上はくじを引く必要がないため E_11 = 0 です。 10 の状態から 11 になるに 1 番目の商品を引かなければなりません。このとき、 5% の確率で引けるので、くじを引く回数の期待値は 100 / 5 回です。もう片方は 95% なので、 100 / 95 回です。

00 からは 5% の確率で 01 になり、 01 からは 100 / 95 回で全て揃います。また、 95% の確率で 10 になり、 10 からは 100 / 5 回で全て揃います。これで、 00 から 11 までの期待値が計算できました。

式を実際に立ててみると、後ろから計算することで解がわかることに気付けます。

あとは式を計算できるように実装します。

実装

sum が自分自身に返ってこない場合の期待値を表しています。 100 / (100 - k) が自分自身に返ってくる確率の逆数（期待値）を表しています。

手計算した式をどうにか実装したらうまくいった、という感じです。

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
const int INF = 1e8;
using namespace std;

//i番目のビットを返す
bool getBit(int num, int i){
	return ((num & (1 << i)) != 0);
}

//i番目を1にする
int setBit(int num, int i){
	return num | (1 << i);
}

int main(){
	int n, m;
	cin >> n >> m;

	vector<int> c(m), cost(m);
	vector<vector<pair<int, int>>> kuji(m); //番号、確率
	rep(i,m){
		cin >> c[i] >> cost[i];
		rep(j,c[i]){
			int a, b;
			cin >> a >> b;
			a--;
			kuji[i].emplace_back(a,b);
		}
	}

	double dp[1 << 10];
	rep(i,1 << 10) dp[i] = INF;
	dp[(1 << n) - 1] = 0;

	for(int s = (1 << n) - 1; s >= 0; s--){
		rep(i,m){
			double sum = cost[i], k = 0;
			for(auto j : kuji[i]){
				if(not getBit(s, j.first)){
					sum += dp[setBit(s, j.first)] * j.second / 100.0;
				}else{
					k += j.second;
				}
			}
			dp[s] = min(dp[s], sum * 100.0 / (100 - k));
		}
	}

	cout << fixed << setprecision(10) << dp[0] << endl;
}