結果

問題 No.309 シャイな人たち (1)
ユーザー koyumeishikoyumeishi
提出日時 2015-12-03 07:05:05
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 792 ms / 4,000 ms
コード長 5,966 bytes
コンパイル時間 800 ms
コンパイル使用メモリ 86,252 KB
実行使用メモリ 19,740 KB
最終ジャッジ日時 2023-10-12 09:26:09
合計ジャッジ時間 11,092 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 784 ms
19,528 KB
testcase_01 AC 780 ms
19,596 KB
testcase_02 AC 782 ms
19,460 KB
testcase_03 AC 781 ms
19,404 KB
testcase_04 AC 12 ms
4,352 KB
testcase_05 AC 176 ms
7,336 KB
testcase_06 AC 592 ms
19,404 KB
testcase_07 AC 787 ms
19,400 KB
testcase_08 AC 783 ms
19,716 KB
testcase_09 AC 782 ms
19,580 KB
testcase_10 AC 792 ms
19,740 KB
testcase_11 AC 787 ms
19,500 KB
testcase_12 AC 787 ms
19,520 KB
testcase_13 AC 2 ms
4,348 KB
testcase_14 AC 2 ms
4,348 KB
testcase_15 AC 115 ms
7,268 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>

#include <cassert>
using namespace std;

#include <bitset>

template<class T>
ostream& operator << (ostream& os, vector<T> vec){
	for(int i=0; i<vec.size(); i++){
		os << (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;

//011011011 -> 111
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 = 0b00011000011000011000011000011000011000011000LL;
						  //0b00000000001111001111001111001111001111001111LL;
constexpr long long maskB = 0b11000000001111000000001111000000001111000000LL;
						  //0b00000000000011111111000011111111000011111111LL;
constexpr long long maskC = 0b11111111000000000000000011111111000000000000LL;
						  //0b00001111111111111111000000001111111111111111LL;
constexpr long long maskD = 0b00001111111111111111000000000000000000000000LL;
constexpr long long maskE = 0b00000000000000000000000000001111111111111111LL;
						  //0b00000000000000000000001111111111111111111111LL;

//011011011 -> 111111
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;
}

long long propagate(long long val, int c){
	long long ret_a = 0;
	{
		ret_a = val;
		int used = 0;
		for(long long i=0; i<c; i++){
			if((used>>i)&1) continue;
			if(((ret_a>>(3LL*i)) & 7LL) >= 3){
				used |= 1<<i;
				ret_a &= ~(7LL<<(3*i));
				ret_a += (1LL<<(3*i+3));
				ret_a += (1LL<<(3*i-3));
				ret_a += (3LL<<(3*i));
				ret_a &= cmask;
			}
		}

		for(long long i=c-1; i>=0; i--){
			if((used>>i)&1) continue;
			if(((ret_a>>(3LL*i)) & 7LL) >= 3){
				used |= 1<<i;
				ret_a &= ~(7LL<<(3*i));
				ret_a += (1LL<<(3*i+3));
				ret_a += (1LL<<(3*i-3));
				ret_a += (3LL<<(3*i));
				ret_a &= cmask;
			}
		}

		for(long long i=10; i>=0; i--){
			if(((ret_a>>(3LL*i)) & 7LL) >= 3){
				ret_a &= ~(7LL<<(3*i));
				ret_a += (3LL<<(3*i));				
			}
		}
	}

	return ret_a;
}

void dfs(vector<int>& memo, int pos, int c, long long val){
	if(pos == c){
		//propagate
		long long val_ = compress_A(val);
		val = propagate(val,c);
		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*3LL)));
	}
}

//00110011 -> 000 111 000 111
long long expander(long long val){
	long long tmp=val;
	val = ((val&(maskD>>8))<<8) | (val&maskE);
	val = ((val&(maskC>>4))<<4) | (val&(maskC>>12));
	val = ((val&(maskB>>2))<<2) | (val&(maskB>>6));
	val = ((val&(maskA>>1))<<1) | (val&(maskA>>3));
	//assert(tmp == compress_A(val));
	return val;
}

void generate_memo(vector<int>& memo, int c){
	for(int i=0; i<(1<<(2*c)); ++i){
		long long val = expander(i);
		long long val_ = compress_A(val);
		val = propagate(val,c);
		int next = compress_B(val);
		memo[val_] =  next;
	}
}

int main(){
	int r,c;
	//cin >> r >> c;
	scanf("%d%d", &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(long long 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(1LL<<(c*2), -1);

	//dfs(memo, 0,c, 0);
	generate_memo(memo, c);

	vector<int> popcount(1LL<<c, 0);
	for(int i=0; i<(1<<c); i++){
		popcount[i] = __builtin_popcount(i);		
	}

	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;

			long long zero = 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){
					if(s[i][j]==4) zero |= 7LL<<(3LL*j);
					state |= max(0LL,4-s[i][j]-1LL) << (3LL*j);
				}else{
					zero |= 7LL<<(3LL*j);
				}
			}
			if(tmp_p<1e-11)continue;

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

				int next = memo[state_];
				int cnt = 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