結果

問題 No.309 シャイな人たち (1)
ユーザー rpy3cpp
提出日時 2016-02-11 15:35:38
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 3,264 bytes
コンパイル時間 867 ms
コンパイル使用メモリ 74,360 KB
実行使用メモリ 17,088 KB
最終ジャッジ日時 2024-09-22 00:35:28
合計ジャッジ時間 11,288 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <deque>
#include <utility>
using namespace std;

constexpr double eps = 1e-20;
int R = 0;
int C = 0;

double solve(const int R, const int C, const vector<vector<double>> & P, const vector<vector<int>> & S);

int get_next_status(int prev, int know, const vector<int> & s);

double calc_prob(int mask, const vector<double> & p);

int bitcount(int mask){
    int counts = 0;
    while (mask){
        if (mask & 1) ++counts;
        mask >>= 1;
    }
    return counts;
}

template <typename T>
void disp(const vector< vector<T> > & mat){
    for (const auto & row : mat){
        for (const auto elem : row){
            cout << elem << ' ';
        }
        cout << endl;
    }
}

int main()
{
    cin >> R >> C;
    vector< vector<int> > S(R, vector<int>(C, 0));
    vector< vector<double> > P(R, vector<double>(C, 0.0));
    // read data
    for (auto & row : P){
        for (auto & p : row){
            cin >> p;
            p /= 100.0;
        }
    }
    for (auto & row : S){
        for (auto & s : row) cin >> s;
    }
    
    // solve
    cout << solve(R, C, P, S) << endl;
    return 0;
}

double solve(const int R, const int C, const vector<vector<double>> & P, const vector<vector<int>> & S){
    double ans = 0;
    vector<double> old_prob(1 << C, 0.0);
    vector<double> new_prob(1 << C, 0.0);
    old_prob[0] = 1.0;
    for (int r = 0; r != R; ++r){
        auto s = S[r];
        auto p = P[r];
        for (int prev = 0; prev != 1 << C; ++prev){
            auto old_p = old_prob[prev];
            if (old_p <= eps) continue;
            for (int know = 0; know != 1 << C; ++know){
                auto new_p = calc_prob(know, p);
                auto new_status = get_next_status(prev, know, s);
                new_prob[new_status] += old_p * new_p;
            }
        }
        for (int status = 0; status != 1 << C; ++status){
            ans += new_prob[status] * bitcount(status);
        }
        swap(old_prob, new_prob);
        for (auto & np : new_prob) np = 0;
    }
    return ans;
}

double calc_prob(int mask, const vector<double> & p){
    double prob = 1.0;
    for (auto pi : p){
        prob *= (mask & 1) ? pi : (1 - pi);
        mask >>= 1;
    }
    return prob;
}

int get_next_status(int prev, int know, const vector<int> & s){
    // prev & (1<<i) : 前列i番目の人が挙手していれば1、挙手していなければ0
    // know & (1<<i) : 当列i番目の人が知っていれば1、知らなければ0
    // s[i] : 恥ずかしがり度
    vector<int> points(C, 0);
    deque<int> changed;
    for (int i = 0; i != C; ++i){
        if (prev & (1<<i)) points[i] += 1;
        if (know & (1<<i)) points[i] += 4 - s[i];
        if (points[i] >= 4) changed.push_back(i);
    }
    while (not changed.empty()){
        auto i = changed.front();
        changed.pop_front();
        if (i){
            points[i - 1] += 1;
            if (points[i - 1] == 4) changed.push_back(i - 1);
        }
        if (i < C - 1){
            points[i + 1] += 1;
            if (points[i + 1] == 4) changed.push_back(i + 1);            
        }
    }
    int ans = 0;
    for (int i = 0; i != C; ++i){
        if (points[i] >= 4) ans += (1<<i);
    }
    return ans;
}
0