結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0