結果

問題 No.309 シャイな人たち (1)
ユーザー 紙ぺーぱー紙ぺーぱー
提出日時 2015-12-05 03:39:29
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,695 bytes
コンパイル時間 487 ms
コンパイル使用メモリ 58,332 KB
実行使用メモリ 20,680 KB
最終ジャッジ日時 2024-09-14 14:18:49
合計ジャッジ時間 5,233 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>

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<=c;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<<ans<<endl;

}
0