結果

問題 No.309 シャイな人たち (1)
ユーザー yumakmcyumakmc
提出日時 2016-02-17 22:03:33
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 1,712 bytes
コンパイル時間 1,379 ms
コンパイル使用メモリ 169,456 KB
実行使用メモリ 13,756 KB
最終ジャッジ日時 2024-09-22 07:42:49
合計ジャッジ時間 11,979 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,587 ms
13,756 KB
testcase_01 TLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
権限があれば一括ダウンロードができます

ソースコード

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

ld pers[11][11];
int shys[11][11];
vector<vector<ld>>hands;
int main() {
	int R, C; cin >> R >> C;
	hands.resize(R+1);
	for (int i = 0; i < hands.size(); ++i){
		hands[i].resize(1 << C);
	}
	for (int i = 0; i < R; ++i){
		for (int j = 0; j < C; ++j){
			cin >> pers[i][j];
			pers[i][j] /= 100;
		}
	}
	for (int i = 0; i < R; ++i){
		for (int j = 0; j < C; ++j){
			cin >> shys[i][j];
		}
	}
	for (int i = 0; i < (1 << C); ++i){
		hands[0][i] = 0;
	}
	hands[0][0] = 1;
	ld ans = 0;
	for (int r = 1; r <= R; ++r){
		for (int l = 0; l < (1 << C); ++l){
			const bitset<11> knows(l); 
			vector<int>points(C);
			ld percentage = 1;
			for (int i = 0; i < C; ++i){
				if (knows[i]){
					points[i] += 4 - shys[r - 1][i];
					percentage *= pers[r - 1][i];
				}
				else{
					percentage *= 1 - pers[r - 1][i];
				}
			}
			
			for (int k = 0; k < (1 << C); ++k){
				if (hands[r - 1][k] < 1e-12)continue;
				vector<int>npoints(points);
				const bitset<11>prehands(k);
				bitset<11>ups(0);
				for (int i = 0; i < C; ++i){
					if (prehands[i]){
						npoints[i] ++;
					}
				}
				for (int i = 0; i < C; ++i){
					
					if (npoints[i] >= 4){
						ups[i] = true;
						if (i != C - 1)npoints[i + 1] ++;
					}
				}
				for (int i = C-1; i >=0; --i){
					if (npoints[i] >= 4){
						ups[i] = true;
						if (i != 0)npoints[i - 1]++;
					}
				}
				hands[r][ups.to_ulong()] += percentage*hands[r - 1][k];
				ans += percentage*hands[r - 1][k] * ups.count();
			}
		}
	}
	cout <<fixed<<setprecision(22)<< ans << endl;
	return 0;
}
0