結果

問題 No.162 8020運動
コンテスト
ユーザー yumakmc
提出日時 2016-02-18 05:39:38
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 689 ms / 5,000 ms
コード長 2,101 bytes
コンパイル時間 1,926 ms
コンパイル使用メモリ 192,584 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-22 07:48:46
合計ジャッジ時間 15,095 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
#include<unordered_map>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;

map<int, map<vector<int>, ld>>pers;

vector<map<vector<int>, ld>>dp;
int main() {
	int A; cin >> A;
	dp.resize(81 - A);
	ld p[3]; cin >> p[0] >> p[1] >> p[2];
	for (int i = 0; i < 3; ++i){
		p[i] /= 100;
	}
	for (int i = 1; i <= 14; ++i){
		for (int j = 0; j < (1 << i); ++j){
			bitset<14>bs(j);
			ld per = 1;
			for (int k = 0; k < i; ++k){
				if (!bs[k]){
					if (i == 1)per *= p[0];
					else if (k == 0 || k == i - 1)per *= p[1];
					else per *= p[2];
				}
				else{
					if (i == 1)per *= 1-p[0];
					else if (k == 0 || k == i - 1)per *= 1-p[1];
					else per *= 1-p[2];
				}
			}
			int num = 0;
			vector<int>vs;
			for (int k = 0; k < i; ++k){
				if (bs[k]){
					num++;
				}
				else{
					if (num){
						vs.push_back(num);
					}
					num = 0;
				}
			}
			if (num){
				vs.push_back(num);
			}
			sort(vs.begin(), vs.end(), greater<int>());
			pers[i][vs] += per;
		}
	}
	dp[0][vector<int>(1, 14)] = 1;
	for (int i = 0; i < 80 - A; ++i){
		for (auto mp : dp[i]){
			vector<map<vector<int>, ld>>mps;
			for (int j = 0; j < mp.first.size(); ++j){
				mps.push_back(pers[mp.first[j]]);
			}
			int num = 1;
			for (auto j : mps){
				num *= j.size();
			}
			for (int j = 0; j < num; ++j){
				vector<int>selects(mps.size());
				int rest = j;
				for (int k = 0; k < mps.size(); ++k){
					selects[k] = rest%mps[k].size();
					rest /= mps[k].size();
				}
				vector<int>ans;
				ld aper = 1;
				for (int k = 0; k < mps.size(); ++k){
					auto it = mps[k].begin();
					while (selects[k]){
						it++;
						selects[k]--;
					}
					ans.insert(ans.end(), it->first.begin(), it->first.end());
					aper *= it->second;
				}
				dp[i + 1][ans] += aper*mp.second;
			}
		}
	}
	ld finans = 0;
	for (auto j : dp[80 - A]){
		int teeth = 0;
		for (int k = 0; k < j.first.size(); ++k){
			teeth += j.first[k];
		}
		finans += j.second*teeth*2;
	}
	cout <<fixed<<setprecision(22)<< finans << endl;
	return 0;
}
0