Official

D - Poker Editorial by tatyam


まだ見えていない \(9K-8\) 枚をそれぞれ区別して考えます。

(高橋くんの勝つ確率) = (高橋くんの勝つ配り方の数) / (全ての配り方の数)
です。
全ての配り方の数は \((9K - 8)(9K - 9)\) なので、高橋くんの勝つ配り方の数が求まれば良いです。

高橋くんに \(x\) 、青木くんに \(y\) を配る方法の数は、\(C_i\) をまだ見えていない \(i\) の枚数として、

\[ \begin{cases} C_xC_y & (x ≠ y)\\ C_x(C_x - 1) & (x = y)\\ \end{cases} \]

なので、高橋くんの勝つ配り方の数は、高橋くんの勝つような \((x, y)\) の組についてこの総和を取れば求められます。

回答例 (C++)

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
using ll = int64_t;

ll score(string S){
    vector<ll> cnt(10);
    iota(cnt.begin(), cnt.end(), 0);
    for(char c : S) cnt[c - '0'] *= 10;
    return accumulate(cnt.begin(), cnt.end(), 0);
}
int main(){
    ll K;
    string S, T;
    cin >> K >> S >> T;
    vector<ll> cnt(10, K);
    for(char c : S + T) cnt[c - '0']--;
    ll win = 0;
    for(ll x = 1; x <= 9; x++) for(ll y = 1; y <= 9; y++){
        S.back() = '0' + x;
        T.back() = '0' + y;
        if(score(S) <= score(T)) continue;
        win += cnt[x] * (cnt[y] - (x == y));
    }
    const ll rem = 9 * K - 8;
    cout << double(win) / rem / (rem - 1) << endl;
}

回答例 (Python)

K = int(input())
S = input()[:4]
T = input()[:4]
cnt = [K] * 10
for c in S:
    cnt[int(c)] -= 1
for c in T:
    cnt[int(c)] -= 1

def score(S):
    cnt = [0] * 10
    for c in S:
        cnt[int(c)] += 1
    ans = 0
    for i in range(1, 10):
        ans += i * 10 ** cnt[i]
    return ans

ans = 0

for i in range(1, 10):
    if cnt[i] == 0:
        continue
    for j in range(1, 10):
        if i == j or cnt[j] == 0:
            continue
        if score(S + str(i)) > score(T + str(j)):
            ans += cnt[i] * cnt[j]

for i in range(1, 10):
    if cnt[i] < 2:
        continue
    if score(S + str(i)) > score(T + str(i)):
        ans += cnt[i] * (cnt[i] - 1)

N = 9 * K - 8
print(ans / N / (N - 1))

posted:
last update: