AOJ 1184. 一般化ポーカー / Generic Poker

解き終わるとやるだけだった気がしてくる。

solution

マッチするものの数と可能な手札の数をそれぞれ求める。 分母側は自明な$O(NML)$ DPで求まり、overflowすることもない。 分子側は面倒。全てのマッチ対象を($0$の位置を無視しての同値関係で割った上で)列挙するので、ざっくりと$O({}_{\min \{ m, 2l - 1 \}}C_{l})$とかだと思う。

分子側について。 例えば手札は$h = (0, 1, 1, 4, 5, 5, 5)$などと関数$h : L \to M$の形で表現することもできるが、そうではなく関数$h’ : M \to \mathbb{N}$の形で$h’ = (1, 2, 0, 0, 1, 3, 0, 0, 0, 0, 0)$のように表すことを考える。 手札の枚数$L \le 7$に対しランクの数$M \le 60$と大きく、そう書いたときはほとんどが$0$である。 パターン指示子a a+ a++ $\dots$は間を飛ばすことなく出現するという制約がある。 このため$h’ = (1, 2, 0, 0, 1, 3, 0, 0, 0, 0, 0)$がマッチするなら$(1, 2, 0, 0, 0, 0, 1, 3, 0, 0, 0)$や$(0, 0, 0, 0, 1, 2, 0, 0, 0, 1, 3)$もマッチ対象。 このように$0$はかなり自由に動かせるので、極力後ろに詰めた形を代表元としてそれだけ列挙するようにする。 例えば$h’$に対しては、末尾の$0$は明らかなので省略して$(1, 2, 0, 1, 3)$がそれ。

$0$で区切られた部分を「ブロック」と呼ぶことにする。 可能なブロックを全て列挙し、それが満たすことのできる変数の集合($a, b, c$の部分集合なので$8$通りであり、複数の可能性がある)も求めておく。 そしてこのブロックを(間に$0$を挟んで)付け加える操作をひとつの遷移とするDPを行ない、マッチする手札の同値類を全て列挙する。 あとはそのまま要素数を計算して足し合わせればよい。

implementation

#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <numeric>
#include <set>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

vector<vector<ll> > calc_choose(int n) { // O(n^2)
    vector<vector<ll> > dp(n + 1);
    dp[0].assign(1, 1);
    repeat (i, n) {
        dp[i + 1].resize(i + 2);
        repeat (j, i + 2) {
            if (j - 1 >= 0) dp[i + 1][j] += dp[i][j - 1];
            if (j != i + 1) dp[i + 1][j] += dp[i][j];
        }
    }
    return dp;
}
constexpr int MAX_M = 60;
auto choose = calc_choose(MAX_M + 1);

vector<int> concat_hands(vector<int> const & xs, vector<int> const & ys) {
    if (xs.empty()) {
        return ys;
    } else {
        assert (not ys.empty());
        vector<int> zs = xs;
        zs.push_back(0);
        for (int y : ys) zs.push_back(y);
        return zs;
    }
}
ll calc_numerator(int n, int m, int l, vector<int> const & a, vector<int> const & b, vector<int> const & c, int star) {
    assert (m <= MAX_M);
    auto f = vectors(8, set<vector<int> >()); // f : used -> sets of lists of hands, where hand : a list of counts. e.g. (1, 1, 2, 2, 2, 3) is (2, 3, 1)
    repeat (star_count, star + 1) {
        repeat (star_set, pow(l, star_count)) {
            vector<int> stars;
            for (int s = star_set; stars.size() < star_count; ) {
                stars.push_back(s % l);
                s /= l;
            }
            if (not whole(is_sorted, stars)) continue;
            repeat_from (ofs_a, -1, l - a.size() + 1) {
                if (a.empty() and ofs_a != -1) break;
                repeat_from (ofs_b, -1, l - b.size() + 1) {
                    if (b.empty() and ofs_b != -1) break;
                    repeat_from (ofs_c, -1, l - c.size() + 1) {
                        if (c.empty() and ofs_c != -1) break;
                        vector<int> used(l);
                        if (ofs_a != -1) repeat (i, a.size()) used[ofs_a + i] += a[i];
                        if (ofs_b != -1) repeat (i, b.size()) used[ofs_b + i] += b[i];
                        if (ofs_c != -1) repeat (i, c.size()) used[ofs_c + i] += c[i];
                        for (int i : stars) used[i] += 1;
                        repeat (i, l) {
                            if (used[i] > n) {
                                used.clear();
                                break;
                            }
                            if (i + 1 < l and not used[i] and used[i + 1]) {
                                used.clear();
                                break;
                            }
                        }
                        while (not used.empty() and used.back() == 0) used.pop_back();
                        if (used.empty()) continue;
                        f[((ofs_a != -1) << 2) | ((ofs_b != -1) << 1) | (ofs_c != -1)].insert(used);
                    }
                }
            }
        }
    }
    int dp_size = min(m, 2 * l - 1);
    auto dp = vectors(dp_size + 1, 8, set<vector<int> >()); // dp : length * used -> hands
    dp[0][(a.empty() << 2) | (b.empty() << 1) | c.empty()].insert(vector<int>());
    set<vector<int> > completed;
    repeat (i, dp_size) repeat (j, 8) for (auto xs : dp[i][j]) {
        repeat (dj, 8) if (not (j & dj)) for (auto ys : f[dj]) {
            int di = ys.size();
            if (not (i + bool(i) + di <= dp_size)) continue;
            vector<int> zs = concat_hands(xs, ys);
            int acc = whole(accumulate, zs, 0);
            if (acc == l) {
                if ((j | dj) == 7) {
                    completed.insert(zs);
                }
            } else if (acc < l) {
                dp[i + bool(i) + di][j | dj].insert(zs);
            }
        }
    }
    ll result = 0;
    for (auto xs : completed) {
        assert (not xs.empty());
        int b = whole(count, xs, 0) + 1;
        int a = m - xs.size() + b;
        ll acc = choose[a][b];
        for (int x : xs) {
            acc *= choose[n][x];
        }
        result += acc;
    }
    return result;
}

ll calc_denominator(int n, int m, int l, vector<int> const & a, vector<int> const & b, vector<int> const & c, int star) {
    auto dp = vectors(m + 1, l + 1, ll());
    dp[0][0] = 1;
    repeat (i, m) {
        repeat (j, l + 1) {
            repeat (d, n + 1) if (j + d <= l) {
                dp[i + 1][j + d] += dp[i][j] * choose[n][d];
            }
        }
    }
    return dp[m][l];
}

int main() {
    while (true) {
        // input
        int n, m, l; cin >> n >> m >> l;
        if (n == 0 and m == 0 and l == 0) break;
        vector<int> a(l), b(l), c(l);
        int star = 0;
        repeat (i, l) {
            string s; cin >> s;
            int rank = s.length() - 1;
            int & it =
                s[0] == 'a' ? a[rank] :
                s[0] == 'b' ? b[rank] :
                s[0] == 'c' ? c[rank] :
                star;
            it += 1;
        }
        while (not a.empty() and a.back() == 0) a.pop_back();
        while (not b.empty() and b.back() == 0) b.pop_back();
        while (not c.empty() and c.back() == 0) c.pop_back();
        // solve
        ll num = calc_numerator(n, m, l, a, b, c, star);
        ll den = calc_denominator(n, m, l, a, b, c, star);
        // output
        printf("%.10Lf\n", num /(long double) den);
    }
    return 0;
}