Submission #1532771


Source Code Expand

Copy
#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

Submission Time
Task C - ソーシャルゲーム
User furuya1223
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2783 Byte
Status AC
Exec Time 2 ms
Memory 256 KB

Judge Result

Set Name A B C D E all
Score / Max Score 10 / 10 10 / 10 10 / 10 20 / 20 20 / 20 30 / 30
Status
AC × 4
AC × 11
AC × 20
AC × 39
AC × 12
AC × 59
Set Name Test Cases
A test_01_ABCDEF.txt, test_02_ABCDEF.txt, test_03_ABCDEF.txt, test_12_ABCDEF.txt
B test_01_ABCDEF.txt, test_02_ABCDEF.txt, test_03_ABCDEF.txt, test_04_BCDF.txt, test_05_BCDF.txt, test_06_BCDF.txt, test_07_BCDF.txt, test_08_BCDF.txt, test_09_BCDF.txt, test_11_BCDF.txt, test_12_ABCDEF.txt
C test_01_ABCDEF.txt, test_02_ABCDEF.txt, test_03_ABCDEF.txt, test_04_BCDF.txt, test_05_BCDF.txt, test_06_BCDF.txt, test_07_BCDF.txt, test_08_BCDF.txt, test_09_BCDF.txt, test_10_CF.txt, test_11_BCDF.txt, test_12_ABCDEF.txt, test_13_CF.txt, test_14_CDF.txt, test_15_CDF.txt, test_16_CF.txt, test_17_CF.txt, test_18_CF.txt, test_25_CDF.txt, test_26_CDF.txt
D test_01_ABCDEF.txt, test_02_ABCDEF.txt, test_03_ABCDEF.txt, test_04_BCDF.txt, test_05_BCDF.txt, test_06_BCDF.txt, test_07_BCDF.txt, test_08_BCDF.txt, test_09_BCDF.txt, test_11_BCDF.txt, test_12_ABCDEF.txt, test_14_CDF.txt, test_15_CDF.txt, test_19_DEF.txt, test_20_DF.txt, test_21_DF.txt, test_22_DF.txt, test_23_DEF.txt, test_24_DF.txt, test_25_CDF.txt, test_26_CDF.txt, test_27_DEF.txt, test_28_DF.txt, test_29_DF.txt, test_30_DF.txt, test_31_DEF.txt, test_32_DF.txt, test_33_DF.txt, test_34_DF.txt, test_35_DEF.txt, test_36_DF.txt, test_37_DF.txt, test_38_DF.txt, test_39_DEF.txt, test_40_DF.txt, test_41_DF.txt, test_42_DF.txt, test_44_DF.txt, test_52_DF.txt
E test_01_ABCDEF.txt, test_02_ABCDEF.txt, test_03_ABCDEF.txt, test_12_ABCDEF.txt, test_19_DEF.txt, test_23_DEF.txt, test_27_DEF.txt, test_31_DEF.txt, test_35_DEF.txt, test_39_DEF.txt, test_49_EF.txt, test_51_EF.txt
all 00_sample_01_F.txt, 00_sample_02_F.txt, 00_sample_03_F.txt, 00_sample_04_F.txt, 00_sample_05_F.txt, test_01_ABCDEF.txt, test_02_ABCDEF.txt, test_03_ABCDEF.txt, test_04_BCDF.txt, test_05_BCDF.txt, test_06_BCDF.txt, test_07_BCDF.txt, test_08_BCDF.txt, test_09_BCDF.txt, test_10_CF.txt, test_11_BCDF.txt, test_12_ABCDEF.txt, test_13_CF.txt, test_14_CDF.txt, test_15_CDF.txt, test_16_CF.txt, test_17_CF.txt, test_18_CF.txt, test_19_DEF.txt, test_20_DF.txt, test_21_DF.txt, test_22_DF.txt, test_23_DEF.txt, test_24_DF.txt, test_25_CDF.txt, test_26_CDF.txt, test_27_DEF.txt, test_28_DF.txt, test_29_DF.txt, test_30_DF.txt, test_31_DEF.txt, test_32_DF.txt, test_33_DF.txt, test_34_DF.txt, test_35_DEF.txt, test_36_DF.txt, test_37_DF.txt, test_38_DF.txt, test_39_DEF.txt, test_40_DF.txt, test_41_DF.txt, test_42_DF.txt, test_43_F.txt, test_44_DF.txt, test_45_F.txt, test_46_F.txt, test_47_F.txt, test_48_F.txt, test_49_EF.txt, test_50_F.txt, test_51_EF.txt, test_52_DF.txt, test_53_F.txt, test_54_F.txt
Case Name Status Exec Time Memory
00_sample_01_F.txt AC 1 ms 256 KB
00_sample_02_F.txt AC 1 ms 256 KB
00_sample_03_F.txt AC 1 ms 256 KB
00_sample_04_F.txt AC 1 ms 256 KB
00_sample_05_F.txt AC 1 ms 256 KB
test_01_ABCDEF.txt AC 1 ms 256 KB
test_02_ABCDEF.txt AC 1 ms 256 KB
test_03_ABCDEF.txt AC 1 ms 256 KB
test_04_BCDF.txt AC 1 ms 256 KB
test_05_BCDF.txt AC 1 ms 256 KB
test_06_BCDF.txt AC 1 ms 256 KB
test_07_BCDF.txt AC 1 ms 256 KB
test_08_BCDF.txt AC 1 ms 256 KB
test_09_BCDF.txt AC 1 ms 256 KB
test_10_CF.txt AC 1 ms 256 KB
test_11_BCDF.txt AC 1 ms 256 KB
test_12_ABCDEF.txt AC 1 ms 256 KB
test_13_CF.txt AC 1 ms 256 KB
test_14_CDF.txt AC 1 ms 256 KB
test_15_CDF.txt AC 1 ms 256 KB
test_16_CF.txt AC 1 ms 256 KB
test_17_CF.txt AC 1 ms 256 KB
test_18_CF.txt AC 1 ms 256 KB
test_19_DEF.txt AC 1 ms 256 KB
test_20_DF.txt AC 1 ms 256 KB
test_21_DF.txt AC 1 ms 256 KB
test_22_DF.txt AC 1 ms 256 KB
test_23_DEF.txt AC 1 ms 256 KB
test_24_DF.txt AC 1 ms 256 KB
test_25_CDF.txt AC 1 ms 256 KB
test_26_CDF.txt AC 1 ms 256 KB
test_27_DEF.txt AC 1 ms 256 KB
test_28_DF.txt AC 1 ms 256 KB
test_29_DF.txt AC 1 ms 256 KB
test_30_DF.txt AC 1 ms 256 KB
test_31_DEF.txt AC 1 ms 256 KB
test_32_DF.txt AC 1 ms 256 KB
test_33_DF.txt AC 1 ms 256 KB
test_34_DF.txt AC 1 ms 256 KB
test_35_DEF.txt AC 1 ms 256 KB
test_36_DF.txt AC 1 ms 256 KB
test_37_DF.txt AC 1 ms 256 KB
test_38_DF.txt AC 1 ms 256 KB
test_39_DEF.txt AC 1 ms 256 KB
test_40_DF.txt AC 1 ms 256 KB
test_41_DF.txt AC 1 ms 256 KB
test_42_DF.txt AC 1 ms 256 KB
test_43_F.txt AC 2 ms 256 KB
test_44_DF.txt AC 1 ms 256 KB
test_45_F.txt AC 1 ms 256 KB
test_46_F.txt AC 1 ms 256 KB
test_47_F.txt AC 2 ms 256 KB
test_48_F.txt AC 1 ms 256 KB
test_49_EF.txt AC 1 ms 256 KB
test_50_F.txt AC 1 ms 256 KB
test_51_EF.txt AC 1 ms 256 KB
test_52_DF.txt AC 1 ms 256 KB
test_53_F.txt AC 2 ms 256 KB
test_54_F.txt AC 1 ms 256 KB