結果

問題 No.309 シャイな人たち (1)
ユーザー koyumeishikoyumeishi
提出日時 2015-12-03 03:22:37
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 4,568 bytes
コンパイル時間 690 ms
コンパイル使用メモリ 85,344 KB
実行使用メモリ 19,940 KB
最終ジャッジ日時 2023-10-12 09:20:21
合計ジャッジ時間 7,251 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;

#include <bitset>
template<class T>
ostream& operator << (ostream& os, vector<T> vec){
	for(int i=0; i<vec.size(); i++){
		os << bitset<22>(vec[i]) << " ";
	}
	return os;
}

constexpr long long mask0 = 0xdb6db6dbLL;	//0b000000011011011011011011011011011011011LL;
constexpr long long mask1 = 0x49249249LL;	//0b000000001001001001001001001001001001001LL;
constexpr long long mask2 = 0x124924924LL;	//0b000000100100100100100100100100100100100LL;

constexpr long long mask3 = 0x104104104LL;	//0b000000100000100000100000100000100000100LL;
										  	//0b000000001100001100001100001100001100001LL;

constexpr long long mask4 = 0x60060060LL; 	//0b000000001100000000001100000000001100000LL;
										  	//0b000000000000111100000000111100000000111LL;

constexpr long long mask5 = 0x7800007800LL;	//0b111100000000000000000000111100000000000LL;
										  	//0b000000000000111100000000000000001111111LL;

constexpr long long mask6 = 0x7F800000LL;	//0b000000001111111100000000000000000000000LL;

int compress_B(long long val){
	val = (val+mask1)&mask2;	//only carry(4)
	val = ((val&mask3)>>2) | (val&(mask3>>3));
	val = ((val&mask4)>>4) | (val&(mask4>>6));
	val = ((val&mask5)>>8) | (val&(mask5>>12));
	val = ((val&mask6)>>16) | (val&(mask6>>24));
	return val;
}

long long cmask;
						  //0b00000000000011011011011011011011011011011011LL;
constexpr long long maskA = 0b00000000011000011000011000011000011000011000LL;
						  //0b00000000001111001111001111001111001111001111LL;
constexpr long long maskB = 0b00000000001111000000001111000000001111000000LL;
						  //0b00000000000011111111000011111111000011111111LL;
constexpr long long maskC = 0b11111111000000000000000011111111000000000000LL;
						  //0b00001111111111111111000000001111111111111111LL;
constexpr long long maskD = 0b00001111111111111111000000000000000000000000LL;
constexpr long long maskE = 0b00000000000000000000000000001111111111111111LL;

int compress_A(long long val){
	val = ((val&maskA)>>1) | (val&(maskA>>3));
	val = ((val&maskB)>>2) | (val&(maskB>>6));
	val = ((val&maskC)>>4) | (val&(maskC>>12));
	val = ((val&maskD)>>8) | (val&maskE);
	return val;
}


void dfs(vector<int>& memo, int pos, int c, long long val){
	if(pos == c){
		//propagate
		long long val_ = compress_A(val);

		long long hoge = val + mask1;	//make 4
		hoge = hoge&mask2;				//find carry
		val = val + (hoge<<1);			//left shift
		hoge = val&mask2;				//find carry
		hoge = hoge | (hoge>>1) | (hoge>>2);
		val ^= hoge;					//flip 4
		val &= cmask;

		hoge = val + mask1;				//right
		hoge = hoge&mask2;
		val = val + (hoge>>5);
		hoge = val&mask2;
		hoge = hoge|(hoge>>1)|(hoge>>2);
		val ^= hoge;
		val &= cmask;

		int next = compress_B(val);
		memo[val_] = next;
		return;
	}
	for(long long i=0; i<=3; i++){
		dfs(memo, pos+1, c, val + (i<<(pos*3)));
	}
}

#include <cassert>
int main(){
	int r,c;
	cin >> r >> c;

	cmask = (1LL<<(3*c))-1;

	vector<vector<int>> p(r, vector<int>(c));
	for(int i=0; i<r; i++){
		for(int j=0; j<c; j++){
			scanf("%d", &p[i][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++){
			scanf("%d", &s[i][j]);
			//cin >> s[i][j];
		}
	}

	vector<long long> expand(1<<c, 0);
	for(int i=0; i<(1<<c); i++){
		long long val = 0;
		for(long long j=0; j<c; j++){
			val += ((i>>j)&1LL)<<(3LL*j);
		}
		expand[i] = val;
	}


	vector<int> memo(1<<(c*2), 0);
	dfs(memo, 0,c, 0);

	vector<double> Prob(1<<c, 0);
	vector<double> Prob_(1<<c, 0);
	Prob[0] = 1.0;

	vector<double> dp(1<<c, 0);
	vector<double> dp_(1<<c, 0);

	for(int i=0; i<r; i++){
		fill(Prob_.begin(), Prob_.end(), 0.0);
		fill(dp_.begin(), dp_.end(), 0.0);

		for(int w=0; w<(1<<c); ++w){
			double tmp_p = 1.0;
			long long state = 0;

			for(long long j=0; j<c; ++j){
				tmp_p *= (((w>>j)&1)?p[i][j]:100-p[i][j]) * 0.01;
				if((w>>j)&1){
					state += max(0,3-s[i][j]) << (3LL*j);
				}
			}

			for(int v=0; v<(1<<c); ++v){
				long long state_ = state + expand[v];
				long long hoge = state_&mask2;
				state_ ^= hoge|(hoge>>1)|(hoge>>2);

				int next = memo[compress_A(state_)];
				int cnt = __builtin_popcount(next);
				dp_[next] += (dp[v] + cnt * Prob[v]) * tmp_p;
				Prob_[next] += Prob[v] * tmp_p;
			}
		}

		swap(dp, dp_);
		swap(Prob, Prob_);
	}

	double ans = 0;
	for(int i=0; i<(1<<c); i++){
		ans += dp[i];
	}
	printf("%.18f\n", ans);
	return 0;
}
0