AOJ1184 一般化ポーカー
見かけに反して結構面白い。
まずはじめに、420個から7個選ぶ場合の数はlong longに収まるので、条件を満たす場合の数を数えることにする。
主要アイデアは、「ランクiまでのカードのうちj枚を使い、a,b,cの3つの系列がカバーされているかされていないかの組(8通り)のうち、どれがあり得てどれがあり得ないかの組(256通り)」をキーにしたDP。つまり状態は{a,b,c}のべき集合のべき集合になる。
これをするために、まず「すべての項が1以上N以下の整数列であり、項の合計がL以下」なものをすべて列挙する。これは、「カードを選んだ時の、ランクが連続している部分のかたち」を表している。
a,b,cの系列のべき集合(すなわち、この列を使ってどの系列をカバーし、どの系列をカバーしないかの組)の元に対して、この列がそのカバーの方法をとることがあり得るかどうかというのは簡単に求められる。
自分の日本語力に限界を感じたので具体例で説明する。
a,a,b,b+,c,c,c+というのがあったとする。
列(1,3,2)は、適当なkに対し、ランクkのカードが1枚、k+1のカードが3枚、k+2のカードが2枚ある状態を表す。簡単のため、この6枚のカードのランクが(0,1,1,1,2,2)であるとする。
ここから{a,a}, {b,b+}, {c,c,c+}という集合の組のうちどれがとれるかを考える。
空集合は当然とれる。
{a}は、a=1とすればよい。
{b}は、b=0とすればよい。
{a,b}は、a=1,b=0とすればよい。
{c}は、c=1とすればよい。
{a,c}はとれない。
{b,c}は、b=c=1とすればよい。
{a,b,c}はとれない。
よって、この列は{a,c}と{a,b,c}以外の系列をカバーできることが分かる。
これを使って場合の数DPをすると解ける。オーダーはM*L*(整数列の数(maxでも64個くらい))*2^(2^3)となる。
#include<stdio.h> #include<vector> #include<algorithm> #include<string> #include<iostream> using namespace std; int gen, num, len; typedef long long ll; typedef pair<int, ll>pii; vector<int>vec[3]; int ast; bool ismatch(vector<int>v, vector<int>dt) { for (int p = 0; p < 3; p++) { if (dt[p] != 0) { dt[p] = 0; bool ret = false; for (int i = 0; i <= v.size(); i++) { vector<int>zv = v; bool f = true; for (int j = 0; j < vec[p].size(); j++) { if (vec[p][j] + i >= v.size()) { f = false; break; } zv[vec[p][j] + i]--; if (zv[vec[p][j] + i] < 0) { f = false; break; } } if (f)ret |= ismatch(zv, dt); } return ret; } } return true; } vector<pii>dat[8][8]; ll com[500][500]; void calc(vector<int>v, int pt) { int cnt = 0; for (int i = 0; i < v.size(); i++)cnt += v[i]; int r = 0; for (int i = 0; i < 8; i++) { vector<int>z; for (int j = 0; j < 3; j++) { if ((i&(1 << j)) != 0)z.push_back(1); else z.push_back(0); } if (ismatch(v, z))r |= (1 << i); } ll tim = 1; for (int i = 0; i < v.size(); i++) { tim *= com[gen][v[i]]; } dat[v.size()][cnt].push_back(make_pair(r,tim)); //printf("///"); //for (int i = 0; i < v.size(); i++)printf("%d ", v[i]); //printf(" %d\n",r); for (int i = 1; i <= min(gen, len - cnt); i++) { v.push_back(i); calc(v, pt + 1); v.pop_back(); } } ll dp[70][8][256]; int gto[256][256]; int main() { for (int i = 0; i < 500; i++) { com[i][0] = 1; for (int j = 1; j <= i; j++) { com[i][j] = com[i - 1][j - 1] + com[i - 1][j]; } } for (int i = 0; i < 256; i++) { for (int j = 0; j < 256; j++) { int to = 0; for (int x = 0; x < 8; x++) { for (int y = 0; y < 8; y++) { if ((i&(1 << x)) != 0 && (j & (1 << y)) != 0) { to |= (1 << (x | y)); } } } gto[i][j] = to; } } for (;;) { scanf("%d%d%d", &gen, &num, &len); if (gen == 0 && num == 0 && len == 0)return 0; for (int i = 0; i < 3; i++)vec[i].clear(); ast = 0; for (int i = 0; i < len; i++) { string s; cin >> s; if (s == "*")ast++; else { if (s[0] == 'a')vec[0].push_back(s.size() - 1); if (s[0] == 'b')vec[1].push_back(s.size() - 1); if (s[0] == 'c')vec[2].push_back(s.size() - 1); } } for (int i = 0; i < 8; i++)for (int j = 0; j < 8; j++)dat[i][j].clear(); vector<int>zzd; calc(zzd, 0); for (int i = 0; i < 70; i++)for (int j = 0; j < 8; j++)for (int k = 0; k < 256; k++)dp[i][j][k] = 0; dp[0][0][1] = 1; for (int i = 0; i <= num; i++) { for (int j = 0; j <= len; j++) { for (int k = 0; k < 256; k++) { for (int p = 0; p <= len; p++) { for (int q = 0; q <= len - j; q++) { for (int r = 0; r < dat[p][q].size(); r++) { //if (dp[i][j][k] != 0)printf("%d %d %d %d %d\n", i, j, k, dp[i][j][k], to); dp[i + p + 1][j + q][gto[k][dat[p][q][r].first]] += dp[i][j][k]*dat[p][q][r].second; } } } } } } ll cnt = 0; for (int i = 128; i < 256; i++) { cnt += dp[num + 1][len][i]; } //printf("%lld %lld\n", cnt, com[gen*num][len]); printf("%.10lf\n", double(cnt) / double(com[gen*num][len])); } }
