ABC193 D - Poker

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import datetime

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def it(): return tuple(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def point(counter):
    p = 0
    for i in range(1, 10):
        p += i * 10 ** counter[i]
    return p


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    K = ii()
    S = iss()
    T = iss()

    all_cards = collections.Counter(list(range(1, 10)) * K)
    s_cards = collections.defaultdict(int)
    t_cards = collections.defaultdict(int)
    # あらかじめ、場に存在するカードの枚数と
    # 高橋くん、青木くんが各々所持するカード枚数をカウント
    for s in S:
        if s == '#':
            continue
        if all_cards[int(s)] > 0:
            all_cards[int(s)] -= 1
        s_cards[int(s)] += 1
    for t in T:
        if t == '#':
            continue
        if all_cards[int(t)] > 0:
            all_cards[int(t)] -= 1
        t_cards[int(t)] += 1

    win, al = 0, 0
    for i in range(1, 10):
        if all_cards[i] == 0:
            continue
        # 青木くんが値iのカードを選択
        all_cards[i] -= 1
        t_cards[i] += 1
        tp = point(t_cards)
        for j in range(1, 10):
            if all_cards[j] == 0:
                continue
            # 高橋くんが値jのカードを選択
            s_cards[j] += 1
            sp = point(s_cards)
            if sp > tp:
                # 高橋くんが値jのカード、青木くんが値iのカードを選択して
                # 高橋くんが勝つ通り数はjのカード枚数 × iのカード枚数
                win += all_cards[j] * (all_cards[i] + 1)
            # 高橋くんが値jのカード、青木くんが値iのカードを選択する通り数は
            # jのカード枚数 × iのカード枚数
            al += all_cards[j] * (all_cards[i] + 1)
            s_cards[j] -= 1
        t_cards[i] -= 1
        all_cards[i] += 1
    print(win / al)


if __name__ == '__main__':
    main()

考え方

問題自体は普通に確立を求める問題ですが、
カード枚数の管理が必要となるため、割と実装力を問われる問題。

---

まず、何を求めるか考えます。
高橋くんが勝つ確率は高橋くんが勝つ通り数 ÷ 選択できるカードの通り数です。
高橋くんが勝つ通り数は高橋くんが値jのカード、青木くんが値iのカードを選択したとき、
jのカード枚数 × iのカードの枚数です。
同様に、選択できるカードの通り数はjのカード枚数 × iのカードの枚数です。

あとはカードの枚数から上記の通り数を求めるだけです。
ただし、高橋くんや青木くんがカードを選択したとき、
カードの枚数が変化するため枚数の管理に気を付ける必要があります。