ARC 016 C - ソーシャルゲーム

問題文 : ソーシャルゲーム

解法 :
$dp[S] :=$ 集合$S$ 内のアイテムを得ていたとして, 残りを全部揃えるための期待値, とすると, ガチャ$i$ から得ようとしている商品の集合$T$ ($T \cap S = \phi$) にたいして,

$dp[S] := \min \left (\dfrac{cost_i}{\sum_{j \in T}prob_{ij}} + \sum_{j \in T} dp[S \cup j] \times \dfrac{prob_{ij}}{\sum_{j \in T}prob_{ij}} \right )$

となる. 計算量は $O(2^{2n}mn)$ ≒ 4 * 10^7 程度なので間に合う.

コード :

#include <cstdio>
#include <vector>

using namespace std;

int N, M;
int C[4], cost[4];
int prob[4][10] = {{0}};
double memo[1025];

void binary(int x)
{
	for (int i = 5; i >= 0; i--) printf("%d ", x >> i & 1);
	printf("\n");
}

double f(int bits)
{
	if (memo[bits] >= 0) return (memo[bits]);
	if (bits == (1 << N) - 1) return (0);
	
	double ret = 1e18;
	for (int i = 1; i < (1 << N); i++){
		if (i != bits && (i & bits) == bits){
			for (int j = 0; j < M; j++){
				vector<pair<int, int> > tmp;
				int sum = 0;
				double ta;
				for (int k = 0; k < N; k++){
					if (bits >> k & 1) continue;
					if ((i >> k & 1) && !prob[j][k]) goto next;
					tmp.push_back(make_pair(prob[j][k], k));
					sum += prob[j][k];
				}
				ta = cost[j] * 100.0 / sum;
				for (int k = 0; k < tmp.size(); k++){
					ta += tmp[k].first * 1.0 / sum * f(bits | (1 << tmp[k].second));
				}
				ret = min(ret, ta);
				next:;
			}
		}
	}
	
	return (memo[bits] = ret);
}

int main()
{
	scanf("%d %d", &N, &M);
	
	for (int i = 0; i < M; i++){
		scanf("%d %d", C + i, cost + i);
		for (int j = 0; j < C[i]; j++){
			int x, y;
			scanf("%d %d", &x, &y);
			prob[i][--x] = y;
		}
	}
	
	for (int i = 0; i < 1 << N; i++) memo[i] = -1;
	
	printf("%.10lf\n", f(0));
	
	return (0);
}