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: