結果

問題 No.309 シャイな人たち (1)
ユーザー 紙ぺーぱー紙ぺーぱー
提出日時 2015-12-05 03:44:23
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 373 ms / 4,000 ms
コード長 1,731 bytes
コンパイル時間 445 ms
コンパイル使用メモリ 64,028 KB
実行使用メモリ 20,544 KB
最終ジャッジ日時 2023-10-12 15:33:52
合計ジャッジ時間 5,634 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 362 ms
20,464 KB
testcase_01 AC 338 ms
20,444 KB
testcase_02 AC 344 ms
20,456 KB
testcase_03 AC 338 ms
20,500 KB
testcase_04 AC 6 ms
4,348 KB
testcase_05 AC 78 ms
9,956 KB
testcase_06 AC 346 ms
20,304 KB
testcase_07 AC 348 ms
20,412 KB
testcase_08 AC 345 ms
20,324 KB
testcase_09 AC 348 ms
20,364 KB
testcase_10 AC 369 ms
20,476 KB
testcase_11 AC 373 ms
20,544 KB
testcase_12 AC 362 ms
20,448 KB
testcase_13 AC 2 ms
4,352 KB
testcase_14 AC 2 ms
4,352 KB
testcase_15 AC 81 ms
9,852 KB
権限があれば一括ダウンロードができます

ソースコード

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