tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

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);
	}
}