[AtCoder] ABC 193 D – Poker

2021年2月28日

問題

方針

高橋君がカード \( i \) を引いて、青木君がカード \( j \) を引く確率を考えます。高橋君と青木が持っているカード \( i \) の枚数をそれぞれ \( s_i , \ t_i\) とします。

• \( i = j \) のとき

このとき、

\[ \dfrac{(K – s_i – t_i)(K – s_i – t_i – 1)}{(9K – 8)(9K – 9)}\]

となります。

\( i \neq j \) のとき

このとき、

\[ \dfrac{(K – s_i – t_i)(K – s_j – t_j)}{(9K – 8)(9K – 9)}\]

となります。したがって、\( i, j \) について全探索します。

コード

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

// 累乗
ll my_pow(ll x, ll n) {
    if (n == 0) return 1;
    if (n % 2 == 0) return my_pow(x * x, n / 2);
    return x * my_pow(x, n - 1);
}

int main() {
    ll K;
    string S, T;
    cin >> K >> S >> T;
    ll c1[9] = {};
    ll c2[9] = {};
    for (int i = 0; i < 4; i++) {
        c1[S[i] - '1']++;
        c2[T[i] - '1']++;
    }
    double ans = 0;
    ll n = 0;

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            ll p1 = 0;
            ll p2 = 0;
            if (i == j && c1[i] + c2[j] + 2 > K) {
                continue;
            } else if (c1[i] + c2[i] + 1 > K || c1[j] + c2[j] + 1 > K) {
                continue;
            }
            c1[i]++;
            c2[j]++;
            for (int k = 0; k < 9; k++) {
                p1 += (k + 1) * my_pow(10, c1[k]);
                p2 += (k + 1) * my_pow(10, c2[k]);
            }
            c1[i]--;
            c2[j]--;
            if (p1 > p2) {
                if (i == j) {
                    n += (K - c1[i] - c2[j]) * (K - c1[i] - c2[j] - 1);
                } else {
                    n += (K - c1[i] - c2[i]) * (K - c1[j] - c2[j]);
                }
            }
        }
    }
    cout << (double) n / ((9 * K - 8) * (9 * K - 9)) << "\n";
    return 0;
}