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