AOJ 1184: 一般化ポーカー
0差、1差、2以上差の3つに分けて全探索。
言われてみればなるほどという感じだし、このくらい思いつくべきでは……
#include<stdio.h> #include<algorithm> using namespace std; char in[10][10]; int pl[10]; int u[10][10]; int t3[10]; int q[10]; int used[10]; int L; int dfs(int a){ if(a==3){ return 1; } if(u[a][0]==0)return dfs(a+1); for(int i=0;i<L;i++){ if(used[i])continue; bool ok=true; for(int j=0;j<L;j++){ int cnt=0; for(int k=0;k<L;k++){ if(!used[k]&&q[k]==q[i]+j)cnt++; } if(cnt<u[a][j])ok=false; } if(ok){ for(int j=0;j<L;j++){ int cnt=0; for(int k=0;k<L;k++){ if(cnt==u[a][j])break; if(!used[k]&&q[k]==q[i]+j){ cnt++; used[k]=1; } } } if(dfs(a+1))return 1; for(int j=0;j<L;j++){ int cnt=0; for(int k=0;k<L;k++){ if(cnt==u[a][j])break; if(used[k]&&q[k]==q[i]+j){ cnt++; used[k]=0; } } } } } return 0; } long long C[10][10]; int main(){ int a,b,c; t3[0]=1; C[0][0]=1; for(int i=0;i<9;i++){ for(int j=0;j<=i;j++){ C[i+1][j]+=C[i][j]; C[i+1][j+1]+=C[i][j]; } } for(int i=1;i<10;i++)t3[i]=t3[i-1]*3; while(scanf("%d%d%d",&a,&b,&c),a){ L=c; for(int i=0;i<10;i++)for(int j=0;j<10;j++)u[i][j]=0; for(int i=0;i<c;i++){ scanf("%s",in[i]); pl[i]=0; for(int j=1;in[i][j];j++)pl[i]++; if(in[i][0]!='*')u[in[i][0]-'a'][pl[i]]++; } /* for(int i=0;i<3;i++){ for(int j=0;j<7;j++)printf("%d ",u[i][j]); printf("\n"); }*/ long long ret=0; for(int i=0;i<t3[c-1];i++){ q[0]=0; for(int j=0;j<c;j++)used[j]=0; for(int j=1;j<c;j++){ q[j]=q[j-1]+i%t3[j]/t3[j-1]; } if(!dfs(0))continue; long long tmp=1; int now=0; int div=1; int num=1; for(int j=0;j<c;j++){ if(j&&q[j]!=q[j-1]){ tmp*=C[a][now]; now=1; num++; if(q[j-1]+1<q[j])div++; }else now++; } tmp*=C[a][now]; int un=b-num; if(un<div-1)continue; un-=div-1; for(int j=0;j<div;j++){ tmp*=(un+div-j); tmp/=(j+1); } // for(int j=0;j<c;j++)printf("%d ",q[j]); // printf(": %lld\n",tmp); ret+=tmp; } long long total=1; for(int i=0;i<c;i++){ total*=(a*b-i); total/=(i+1); } printf("%.12f\n",(double)ret/total); } }