結果

問題 No.309 シャイな人たち (1)
コンテスト
ユーザー 紙ぺーぱー
提出日時 2015-12-05 03:44:23
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 360 ms / 4,000 ms
コード長 1,731 bytes
コンパイル時間 534 ms
コンパイル使用メモリ 64,476 KB
実行使用メモリ 20,608 KB
最終ジャッジ日時 2024-09-14 14:19:12
合計ジャッジ時間 5,486 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <iomanip>
using namespace std;

int r,c, A[12][12];
double dp[12][1<<12],P[12][12],p[12][1<<12];
int stand[1<<22],dame[1<<12];

int main(){
  cin>>r>>c;
  //input
  for(int i=0;i<r;i++)
    for(int j=0;j<c;j++)
      cin>>P[i][j];
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      cin>>A[i][j];
      if(A[i][j]==4){
        A[i][j]=0;
        P[i][j]=0;
      }
      P[i][j]/=100;
    }
  }

  //or mask
  for(int i=0;i<1<<c;i++){
    for(int j=0;j<c;j++){
      if((i>>j&1)==0)dame[i]=dame[i]*4+3;
      else dame[i]*=4;
    }
  }
  //pattern
  for(int i=0;i<r;i++){
    for(int j=0;j<1<<c;j++){
      double v=1.0;
      for(int k=0;k<c;k++){
        if(j>>k&1)v*=P[i][k];
        else v*=1-P[i][k];
      }
      p[i][j]=v;
      //cout<<j<<" "<<v<<endl;;
    }
  }

  //stand
  for(int i=0;i<1<<(2*c);i++){

    int a[12];
    for(int j=0;j<(2*c);j+=2){
      a[j/2]=(i>>j)&3;
    }
    for(int j=0;j<c-1;j++){
      if(a[j]<=0)a[j+1]--;
    }
    for(int j=c-1;j>0;j--){
      if(a[j]<=0)a[j-1]--;
    }
    int go=0;
    for(int j=0;j<c;j++){
      go=(go<<1)+(a[j]<=0);
    }
    stand[i]=go;
  }
  //dp
  dp[0][0]=1.0;
  for(int i=0;i<r;i++){
    //pre stand
    for(int j=0;j<1<<c;j++){
      //need to stand
      int mask=0;
      for(int k=0;k<c;k++){
        int v=A[i][k];
        if(v&&(j>>k&1))v--;
        mask=(mask<<2)+v;
      }
      //know
      for(int k=0;k<1<<c;k++){
        int go=mask|dame[k];
        dp[i+1][stand[go]]+=p[i][k]*dp[i][j];
      }

    }
  }
  double ans=0.0;
  for(int i=1;i<=r;i++){
    for(int j=0;j<1<<c;j++){
      int add=0;
      for(int k=0;k<c;k++)if(j>>k&1)add++;
      ans+=add*dp[i][j];
    }
  }
  cout<<setprecision(20)<<ans<<endl;

}
0