結果

問題 No.309 シャイな人たち (1)
ユーザー rpy3cpprpy3cpp
提出日時 2016-02-12 03:48:29
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 978 ms / 4,000 ms
コード長 4,033 bytes
コンパイル時間 917 ms
コンパイル使用メモリ 79,612 KB
実行使用メモリ 19,752 KB
最終ジャッジ日時 2024-09-22 04:04:25
合計ジャッジ時間 12,270 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 978 ms
19,752 KB
testcase_01 AC 799 ms
19,656 KB
testcase_02 AC 909 ms
19,612 KB
testcase_03 AC 831 ms
19,672 KB
testcase_04 AC 12 ms
6,940 KB
testcase_05 AC 166 ms
7,312 KB
testcase_06 AC 356 ms
19,748 KB
testcase_07 AC 971 ms
19,700 KB
testcase_08 AC 883 ms
19,592 KB
testcase_09 AC 924 ms
19,596 KB
testcase_10 AC 966 ms
19,596 KB
testcase_11 AC 966 ms
19,748 KB
testcase_12 AC 969 ms
19,700 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 1 ms
6,944 KB
testcase_15 AC 6 ms
7,440 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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);

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

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

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;
}

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;
            auto points = calc_points(know, s);
            for (int prev = 0; prev != limit; ++prev){
                auto new_status = next_status[get_next_status(prev, points)];
                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);
        int head_result_on = 1 << c;
        for (auto head : {1, 2, 3}){
            int head_mask = head << (2 * c);
            int head_result2 = (head >= 2) ? head_result_on : 0;
            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;
}

vector<int> calc_points(int know, const vector<int> & s){
    vector<int> points;
    for (int i = 0; i != C; ++i){
        if (know & (1 << i)){
            points.push_back(3 - s[i]);
        }else{
            points.push_back(-1);
        }
    }
    return points;
}

int get_next_status(int prev, const vector<int> & points){
    int ans = 0;
    for (int i = 0; i != C; ++i){
        int p = points[i];
        if (p < 0) continue;
        if (prev & (1 << i) and p < 3) ++p;
        ans += (p << (2 * i));
    }
    return ans;
}
0