結果

問題 No.309 シャイな人たち (1)
コンテスト
ユーザー rpy3cpp
提出日時 2016-02-12 03:11:03
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 1,196 ms / 4,000 ms
コード長 4,170 bytes
コンパイル時間 953 ms
コンパイル使用メモリ 78,284 KB
実行使用メモリ 19,804 KB
最終ジャッジ日時 2024-09-22 04:03:49
合計ジャッジ時間 15,186 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <deque>
#include <utility>
#include <iomanip>
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);

vector<int> preprocess(int n_col);

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 << fixed << setprecision(12);
    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){
    auto next_status = preprocess(C);
    double ans = 0;
    int limit = 1 << C;
    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 know = 0; know != limit; ++know){
            auto new_p = calc_prob(know, p);
            if (new_p <= eps) continue;
            for (int prev = 0; prev != limit; ++prev){
                auto new_status = next_status[get_next_status(prev, know, s)];
                new_prob[new_status] += old_prob[prev] * 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;
}

vector<int> preprocess(int n_col){
    vector<int> next_status(1 << (2 * n_col), 0);
    next_status[3] = 1;
    for (int c = 1; c != n_col; ++c){
        int tail_limit = 1 << (2 * c - 2);
        for (auto head : {1, 2, 3}){
            int head_mask = head << (2 * c);
            int head_result2 = (head >= 2) ? (1 << c) : 0;
            int head_result_on = 1 << c;
            for (auto neck : {0, 1, 2, 3}){
                int neck_mask = neck << (2 * c - 2);
                int neck_tail_limit = neck_mask + tail_limit;
                int neck_threshold = 1 << (c - 1);
                for (int neck_tail = neck_mask; neck_tail != neck_tail_limit; ++neck_tail){
                    int prev = next_status[neck_tail];
                    if (prev >= neck_threshold){
                        next_status[head_mask | neck_tail] = head_result2 + prev;
                    } else if (head != 3){
                        next_status[head_mask | neck_tail] = prev;
                    } else {
                        next_status[head_mask | neck_tail] = head_result_on + next_status[neck_tail + tail_limit];
                    }
                }
            }
        }
    }
    return next_status;
}

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] : 恥ずかしがり度
    int ans = 0;
    for (int i = 0; i != C; ++i){
        if ((know & (1 << i)) == 0) continue;
        int tmp = 3 - s[i];
        if (prev & (1 << i)) ++tmp;
        if (tmp <= 0) continue;
        if (tmp == 4) tmp = 3;
        ans += (tmp << (2 * i));
    }
    return ans;
}
0