Submission #1532771

---

Source Code Expand

#include "bits/stdc++.h"
#include <sys/timeb.h>
#include <fstream>

using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define replrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) replrev(i,0,n)
#define repi(itr,ds) for(auto itr=ds.begin();itr!=ds.end();itr++)
#define all(a) a.begin(),a.end()
#define mp make_pair
#define mt make_tuple
#define INF 2000000000
#define INFL 1000000000000000000LL
#define EPS (1e-8)
#define MOD 1000000007
#define PI 3.1415926536
#define RMAX 4294967295

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<P> vP;
typedef vector<vector<int> > vvi;
typedef vector<vector<bool> > vvb;
typedef vector<vector<ll> > vvll;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<double> > vvd;
typedef vector<vector<P> > vvP;
typedef priority_queue<int, vector<int>, greater<int> > pqli;
typedef priority_queue<ll, vector<ll>, greater<ll> > pqlll;
typedef priority_queue<P, vector<P>, greater<P> > pqlP;
/*
// シンプルな構文解析用
typedef string::const_iterator State;
class ParseError {};
//*/
struct Edge {
	int from, to, cost;
	bool operator<(Edge e) {
		return cost < e.cost;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

int N, M;
vi C, cost;
vvi idol, p;
vd dp;

double calc(int state) {
	if (dp[state] + EPS >= 0) {
		return dp[state];
	}

	double minimum = INF;
	rep(i, M) {
		// i番目のガチャでの期待値
		double success = 0;	// 未入手のアイドルを獲得できる（足踏みしない）確率
		double expect = 0;
		rep(j, C[i]) {
			if ((state & (1 << idol[i][j])) == 0) {
				// j番目のアイドルが未入手のとき
				success += p[i][j] / 100.0;
			}
		}
		if (success <= EPS) {
			// 新たなアイドルを入手できないとき
			continue;
		}
		rep(j, C[i]) {
			if ((state & (1 << idol[i][j])) == 0) {
				// j番目のアイドルが未入手のとき
				expect += p[i][j] / 100.0 / success * calc(state | (1 << idol[i][j]));
			}
		}
		expect += cost[i] / success;
		minimum = min(minimum, expect);
	}
	return dp[state] = minimum;
}

int main(void) {
	cin >> N >> M;
	C = vi(M);
	cost = vi(M);
	idol = vvi(M);
	p = vvi(M);
	rep(i, M) {
		cin >> C[i] >> cost[i];
		idol[i] = vi(C[i]);
		p[i] = vi(C[i]);
		rep(j, C[i]) {
			cin >> idol[i][j] >> p[i][j];
			idol[i][j]--;
		}
	}
	dp = vd(1 << N, -1);
	dp[(1 << N) - 1] = 0;

	cout << fixed << setprecision(14) << calc(0) << endl;

	return 0;
}

Submission Info

Judge Result