2021-03-02

AtCoder ABC 193 D - Poker (緑色, 400 点)

発想や考え方はそんなに難しくないんだけど、すごく頭がこんがらがってしまう問題だね...

問題へのリンク

問題概要

$1, 2, \dots, 9$ が表に書かれたカードが $K$ 枚ずつ、計 $9K$ 枚のカードがあります。

これらのカードをランダムにシャッフルして、高橋くんと青木くんにそれぞれ、4 枚を表向きに、1 枚を裏向きにして配りました。高橋くんに配られたカードが文字列 $S$ として、青木くんに配られたカードが文字列 $T$ として与えられます。 $S, T$ は 5 文字の文字列で、先頭 4 文字は 1, 2, …, 9 からなり、表向きのカードに書かれた数を表します。末尾 1 文字は # であり、裏向きのカードであることを表します。

5 枚の手札の点数を、 $c_i$ をその手札に含まれる $i$ の枚数として、 $\sum_{i=1}^{9} = i \times 10^{c_{i}}$ で定義します。高橋くんが青木くんより点数の高い手札を持っていたら高橋くんの勝ちです。

高橋くんの勝つ確率を求めてください。

制約

$2 \le K \le 10^{5}$

考えたこと

$K \le 10^{5}$ という制約を見ると、計算量に工夫がいるのかなと錯覚してしまうけど、冷静に考えると

$S$ の 5 枚目のカードがどれか (1, 2, ..., 9 の 9 通り)
$T$ の 5 枚目のカードがどれか (1, 2, ..., 9 の 9 通り)

で、考えられる場合が 81 通りしかない。なので、全部試せば OK！！！81 通りそれぞれに対して、

そのパターンが出る確率
高橋くんが勝てるかどうか

を判定できれば OK。後者の「高橋くんが勝てるかどうか」は計算するだけ (ただし 0 回しか登場しない数値にも得点が発生することに注意) なので、前者の「そのパターンが出る確率」を考えよう。

サンプルで確率計算

とりあえずサンプルを使って考えてみよう！サンプル 1 よりもむしろ、サンプル 3 の方が様子を掴みやすい！

6
1122#
2228#

まず、1, 1, 2, 2, 2, 2, 2, 8 を使用した時点で残っているカードは

1 が 4 枚
2 が 1 枚
3 が 6 枚
4 が 6 枚
5 が 6 枚
6 が 6 枚
7 が 6 枚
8 が 5 枚
9 が 6 枚

となっている。合計で 46 枚残っている。1 や 2 の残り枚数が少ないので

「S の最後が 1、T の最後が 2」となる確率
「S の最後が 5、T の最後が 6」となる確率

は等しくならないことに注意しよう。ちゃんと正確に確率を見積もってみよう。まず、ありうるすべての場合の数 (確率の分母) を求めてみる。

まず S に入るカードを選ぶ方法が 46 通り (一般には $9K-8$ 通り)
T に入るカードを残りのカードから選ぶ方法が 45 通り (一般には $9K-9$ 通り)

となるので、全体としては

$46 \times 45 = 2070$ 通り (一般には、 $(9K-8)(9K-9)$ 通り)

となる。ここで、「組合せ」だと誤解して $\frac{46 \times 45}{2} = 1035$ 通りとしてしまわないように注意。今回、選んだ 2 枚のカードをそれぞれ S 側に渡すか T 側に渡すかを区別しないといけない！！！

さてサンプル 3 に戻ると、高橋君が勝てるパターンが

S の最後が 2
T の最後が 1

しかない。そして 2 が残り 1 枚しかないので前者が 1 通りで、1 が残り 2 枚なので後者が 2 通り。よって 2 通り。以上から確率は

$\frac{2}{2070} = \frac{1}{1035}$

になる。

S の最後と T の最後が同じ場合と異なる場合

以上の考察を一般化して整理しよう！！！
まず、全体の場合の数は、先ほどのとおり $(9K-8)(9K-9)$ 通りとなる。

さて、 $9K$ 枚のカードから 8 枚使って残ったカードのうち、 $1, 2, \dots, 9$ の枚数を $c_{1}, c_{2}, \dots, c_{9}$ 枚としよう。 $S$ の最後が $i$ で、 $T$ の最後が $j$ としたとき、もし $i$ と $j$ が異なるならば、単純に $c_{i} \times c_{j}$ 通りとなる。

問題は、 $i = j$ となる場合。このときは

$c_{i} (= c_{j})$ 枚のカードのうち、 $S$ の最後に来るカードを選ぶ方法が $c_{i}$ 通り
その残りの $c_{i}-1$ 枚のカードのうち、 $T$ の最後に来るカードを選ぶ方法が $c_{i}-1$ 通り

となるので、 $c_{i} \times (c_{i} -1)$ 通りとなる。以上をまとめると、次のようになる。

$i \neq j$ のとき、確率は $\frac{c_{i}c_{j}}{(9K-8)(9K-9)}$
$i = j$ のとき、確率は $\frac{c_{i}(c_{i}-1)}{(9K-8)(9K-9)}$

コード

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

long long score(const string &S) {
    vector<long long> val(10);
    for (int v = 1; v <= 9; ++v) val[v] = v;
    for (auto c: S) val[c-'0'] *= 10;
    long long sum = 0;
    for (int v = 1; v <= 9; ++v) sum += val[v];
    return sum;
}

int main() {
    long long K;
    string S, T;
    cin >> K >> S >> T;

    // 残りカード枚数
    vector<long long> rem(10, K);
    for (int i = 0; i < 4; ++i) rem[S[i]-'0']--, rem[T[i]-'0']--;

    double res = 0.0;
    for (int a = 1; a <= 9; ++a) {
        for (int b = 1; b <= 9; ++b) {
            S[4] = (char)('0' + a), T[4] = (char)('0' + b);

            // ひとまず分子だけ合算する
            if (score(S) > score(T)) {
                if (a != b) res += rem[a] * rem[b];
                else res += rem[a] * (rem[a] - 1);
            }
        }
    }
    res /= (K*9-8) * (K*9-9);
    cout << fixed << setprecision(10) << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 193 D - Poker (緑色, 400 点)

問題概要

制約

考えたこと

サンプルで確率計算

S の最後と T の最後が同じ場合と異なる場合

コード