結果

問題 No.309 シャイな人たち (1)
ユーザー koyumeishi
提出日時 2015-12-02 23:22:22
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,840 bytes
コンパイル時間 1,006 ms
コンパイル使用メモリ 93,664 KB
実行使用メモリ 14,016 KB
最終ジャッジ日時 2024-09-14 08:08:55
合計ジャッジ時間 10,776 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 1 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
void propagate(vector<int>& y, int& used, int pos){
    if(pos<0 || pos>=y.size()) return;
    if((used>>pos)&1) return;
    y[pos]++;
    if(y[pos]>=4){
        used |= 1<<pos;
        propagate(y, used, pos-1);
        propagate(y, used, pos+1);
    }
}
void propagate_begin(vector<int>& y, int& used, int pos){
    if(pos<0 || pos>=y.size()) return;
    if((used>>pos)&1) return;
    if(y[pos]>=4){
        used |= 1<<pos;
        propagate(y, used, pos-1);
        propagate(y, used, pos+1);
    }
}
template<class T>
ostream& operator << (ostream& os, vector<T> vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << " ";
    }
    return os;
}
#include <bitset>
int main(){
    int r,c;
    cin >> r >> c;
    vector<vector<int>> p(r, vector<int>(c));
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            cin >> p[i][j];
        }
    }
    vector<vector<int>> s(r, vector<int>(c));
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            cin >> s[i][j];
        }
    }
    vector<double> Prob(1<<c, 0);
    Prob[0] = 1.0;
    vector<double> dp(1<<c, 0);
    for(int i=0; i<r; i++){
        vector<double> dp_(1<<c, 0);
        vector<double> next_Prob(1<<c, 0);
        double hoge = 0;
        for(int w=0; w<(1<<c); w++){
            double tmp_p = 1.0;
            vector<int> y(c, 0);
            int used = 0;
            for(int j=0; j<c; j++){
                tmp_p *= (((w>>j)&1)?p[i][j]:100-p[i][j])/100.0;
                if((w>>j)&1){
                    y[j] = 4-s[i][j];
                }
            }
            if(tmp_p < 1e-18) continue;
            for(int v=0; v<(1<<c); v++){
                if(Prob[v] < 1e-18) continue;
                auto z=y;
                int used_ = used;
                for(int j=0; j<c; j++){
                    z[j] += (v>>j)&1;
                }
                for(int j=0; j<c; j++){
                    if(z[j]>=4 && ((used_>>j)&1)==0){
                        propagate_begin(z,used_,j);
                    }
                }
                int next = 0;
                int cnt = 0;
                for(int j=0; j<c; j++){
                    next |= (z[j]>=4)<<j;
                    cnt += (z[j]>=4);
                }
                dp_[next] += (dp[v] + cnt * Prob[v]) * tmp_p;
                next_Prob[next] += Prob[v] * tmp_p;
            }
        }
        swap(dp, dp_);
        swap(Prob, next_Prob);
    }
    double ans = 0;
    for(int i=0; i<(1<<c); i++){
        ans += dp[i];
    }
    printf("%.18f\n", ans);
    return 0;
}
int main_(){
    int r,c;
    cin >> r >> c;
    vector<vector<int>> p(r, vector<int>(c));
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            cin >> p[i][j];
        }
    }
    vector<vector<int>> s(r, vector<int>(c));
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            cin >> s[i][j];
        }
    }
    vector<vector<double>> Prob(1<<c, vector<double>(c+1, 0.0));
    Prob[0][0] = 1.0;
    //vector<vector<double>> dp(1<<c, vector<double>(r*c+1, 0.0));
    for(int i=0; i<r; i++){
        //vector<vector<double>> dp_(1<<c, vector<double>(r*c+1,0.0));
        vector<vector<double>> Prob_(1<<c, vector<double>((i+1)*c+1,0.0));
        for(int w=0; w<(1<<c); w++){
            double tmp_p = 1.0;
            vector<int> y(c, 0);
            int used = 0;
            for(int j=0; j<c; j++){
                tmp_p *= (((w>>j)&1)?p[i][j]:100-p[i][j])/100.0;
                if((w>>j)&1){
                    y[j] = 4-s[i][j];
                }
            }
            for(int j=0; j<c; j++){
                if(y[j]>=4 && ((used>>j)&1)==0){
                    propagate_begin(y,used,j);
                }
            }
            for(int v=0; v<(1<<c); v++){
                auto z=y;
                int used_ = used;
                for(int j=0; j<c; j++){
                    z[j] += (v>>j)&1;
                }
                for(int j=0; j<c; j++){
                    if(z[j]>=4 && ((used_>>j)&1)==0){
                        propagate_begin(z,used_,j);
                    }
                }
                int next = 0;
                int cnt = 0;
                for(int j=0; j<c; j++){
                    next |= (z[j]>=4)<<j;
                    cnt += (z[j]>=4);
                }
                for(int _=0; _<=i*c; _++){
                    if(Prob[v][_] < 1e-22) continue;
                    //dp_[next][cnt+_] += (dp[v][_] + cnt) * tmp_p;
                    Prob_[next][cnt+_] += Prob[v][_] * tmp_p;
                }
            }
        }
        //swap(dp, dp_);
        swap(Prob, Prob_);
    }
    double ans = 0;
    for(int i=0; i<(1<<c); i++){
        for(int j=0; j<=r*c; j++){
            ans += Prob[i][j] * j;
        }
    }
    printf("%.18f\n", ans);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0