結果

問題 No.309 シャイな人たち (1)
ユーザー koyumeishikoyumeishi
提出日時 2015-12-03 06:11:30
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 973 ms / 4,000 ms
コード長 6,553 bytes
コンパイル時間 985 ms
コンパイル使用メモリ 91,580 KB
実行使用メモリ 20,032 KB
最終ジャッジ日時 2024-09-14 08:22:02
合計ジャッジ時間 13,409 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 944 ms
19,872 KB
testcase_01 AC 934 ms
19,796 KB
testcase_02 AC 942 ms
19,968 KB
testcase_03 AC 932 ms
19,880 KB
testcase_04 AC 15 ms
6,944 KB
testcase_05 AC 203 ms
7,460 KB
testcase_06 AC 924 ms
19,964 KB
testcase_07 AC 942 ms
19,808 KB
testcase_08 AC 926 ms
19,816 KB
testcase_09 AC 973 ms
19,888 KB
testcase_10 AC 946 ms
19,796 KB
testcase_11 AC 946 ms
20,032 KB
testcase_12 AC 939 ms
19,904 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 218 ms
7,576 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:180:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  180 |                         scanf("%d", &p[i][j]);
      |                         ~~~~~^~~~~~~~~~~~~~~~
main.cpp:187:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  187 |                         scanf("%d", &s[i][j]);
      |                         ~~~~~^~~~~~~~~~~~~~~~

ソースコード

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;

//011011011 -> 111111
int compress_A(long long val){
	//val = val&mask0;
	if(val&mask2){
		cerr << bitset<33>(val) << endl;
		assert((val&mask2)==0);
	}
	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){
	long long ret_a = 0;
	{
		ret_a = val;
		int used = 0;
		for(long long i=0; i<11; 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;
			}
		}
	
		ret_a &= cmask;
		for(long long i=10; 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;
			}
		}
		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));				
			}
		}
	}
/*
	long long ret_b = 0;
	{
		ret_b = val;
		vector<long long> v(11);
		vector<int> used(11,0);
		for(long long i=0; i<11; i++){
			v[i] = min(3LL, (ret_b>>(3LL*i)) & 7LL);
		}
		for(long long i=0; i<11; i++){
			if(v[i]>=3 && used[i]==0){
				used[i] = 1;
				if(i+1<11) v[i+1]++;
				if(i-1>=0) v[i-1]++;
			}
		}
	
		for(long long i=10; i>=0; i--){
			if(v[i]>=3 && used[i]==0){
				used[i] = 1;
				if(i+1<11) v[i+1]++;
				if(i-1>=0) v[i-1]++;
			}
		}
	
		ret_b = 0;
		for(long long i=0; i<11; i++){
			v[i] = min(3LL,v[i]);
			ret_b |= v[i]<<(3LL*i);
		}
		ret_b &= cmask;
	}
	if(ret_a!=ret_b){
		cerr << bitset<34>(val) << " : " << bitset<34>(ret_a) << " , " << bitset<34>(ret_b) << endl;
		cerr << bitset<34>(cmask) << endl;
		assert(ret_a == ret_b);
	}
*/

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



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

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

	cerr << "hoge" << endl;

	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;
			long long one = 0;
			long long two = 0;
			long long three = 0;
			long long four = 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);
					if(s[i][j]==3) one  |= 1LL<<(3LL*j);
					if(s[i][j]==2) two  |= 1LL<<(3LL*j);
					if(s[i][j]==1) three|= 2LL<<(3LL*j);
					if(s[i][j]==0) four |= 3LL<<(3LL*j);
				}else{
					zero |= 7LL<<(3LL*j);
				}
			}

			for(int v=0; v<(1<<c); ++v){
				long long state_ = four;
				state_ += ((one + (expand[v]&one) )>>1LL)&mask0;
				state_ += (expand[v]&two) << 1LL;
				state_ += ((~expand[v])&two);
				state_ += three+(expand[v]&(three>>1LL));
				if((state_&mask2) != 0){
					cerr << i<<" "<<w<<" " << v<<endl;
					abort();
				}
				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