[yukicoder] No. 1220 yukipoker

2020年9月18日2020年12月13日

問題

方針

全ての手札の組み合わせは \( {}_{NM} \mathrm{ C }_{K} \) 通りありますが、確率を比較するうえでは必要ありません。フラッシュの総数は、同一のソートから \( {}_{N} \mathrm{ C }_{K} \) 通りあり、\( M \) 種類のソートがあるので、\( M{}_{N} \mathrm{ C }_{K} \) 通りあります。ストレートについては、連番の組み合わせが \( N – K + 1 \) 通りあり、ある数字に対して \( M \) 種類から選べるので、\( (N – K + 1)M^K\) 通りあります。

ここで、

\[ \log {}_{N} \mathrm{ C }_{K} = \log N! – \log K! – \log(N-K)!\]

となります。また、

\[ \log N! = \log 1 + \log 2 + \cdots + \log N\]

となるので、累積和を用いて高速に計算することができます。

したがって、フラッシュの総数の対数を取ったものを \( F \)、ストレートのものを \( S \) とすると、

\begin{eqnarray}
F &=& \log M + \log N! – \log K! – \log(N-K)!\\
S &=& \log (N – K + 1) + K \log M
\end{eqnarray}

を比較すれば良いです。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll N, M, K;
double f[100001]{};

void solve() {
    double F = log(M) + f[N] - f[K] - f[N - K];
    double S = log(M) * K + log(N - K + 1);
    if (F < S) {
        cout << "Flush\n";
    } else {
        cout << "Straight\n";
    }
}

int main() {
    int Q;
    cin >> Q;
    for (int i = 0; i < 100000; i++) {
        f[i + 1] = f[i] + log(i + 1);
    }
    
    for (int i = 0; i < Q; i++) {
        cin >> N >> M >> K;
        solve();
    }

    return 0;
}

感想

階乗の対数を取って計算する問題を以前解いたことがありました。