結果
| 問題 |
No.309 シャイな人たち (1)
|
| ユーザー |
 koyumeishi
|
| 提出日時 | 2015-12-03 06:28:46 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 764 ms / 4,000 ms |
| コード長 | 5,326 bytes |
| コンパイル時間 | 913 ms |
| コンパイル使用メモリ | 91,068 KB |
| 実行使用メモリ | 19,868 KB |
| 最終ジャッジ日時 | 2024-09-14 08:23:07 |
| 合計ジャッジ時間 | 10,783 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 13 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:129:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
129 | scanf("%d%d", &r,&c);
| ~~~~~^~~~~~~~~~~~~~~
main.cpp:136:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
136 | scanf("%d", &p[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~
main.cpp:143:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
143 | scanf("%d", &s[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~
ソースコード
#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&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)));
}
}
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);
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;
}