キャディプログラミングコンテスト2021(ABC193) D - Poker【 Python解答例】
AtCoder Beginner Contest193のD - PokerについてPythonの解答例を記事にしていきます。
atcoder.jp
AtCoder Beginner Contest193 D - Poker
問題文
1,2,…,9 が表に書かれたカードが K 枚ずつ、計 9K 枚のカードがあります。
これらのカードをランダムにシャッフルして、高橋くんと青木くんにそれぞれ、4 枚を表向きに、1 枚を裏向きにして配りました。
高橋くんに配られたカードが文字列 S として、青木くんに配られたカードが文字列 T として与えられます。
S,T は 5 文字の文字列で、先頭 4 文字は 1, 2, …, 9 からなり、表向きのカードに書かれた数を表します。 末尾 1 文字は # であり、裏向きのカードであることを表します。
5 枚の手札の点数を、ci をその手札に含まれる i の枚数として、 で定義します。
高橋くんが青木くんより点数の高い手札を持っていたら高橋くんの勝ちです。
高橋くんの勝つ確率を求めてください。
制約
・2≤K≤10^5
・|S|=|T|=5
・S,T の 1 文字目から 4 文字目は 1, 2, …, 9 のいずれか
・1, 2, …, 9 はそれぞれ、S と T に合計 K 回までしか出現しない
・S,T の 5 文字目は #
解答例
k = int(input()) s = input() s = s[:-1] t = input() t = t[:-1] cnt = [k] * 10 # カードの各枚数 # 表向きカード分だけ枚数をcntから減らす for i in s: cnt[int(i)] -= 1 for j in t: cnt[int(j)] -= 1 # 手持ちカードの得点計算 def score(S): res = 0 for i in range(1,10): tmp = S.count(str(i)) # 数字iのカード枚数 res += i * 10 ** tmp # 得点計算 return res # 高橋君が勝つ場合の数 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] # iと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) # iとi-1のかけた値が勝つ場合の数 n = 9 * k - 8 # 未確認のカード枚数 print(ans / n / (n-1))
解説
高橋君と青木君がポーカーをしていてそれぞれ5枚配られます。
そのうち4枚は表向きで数字が確定していますが、残り1枚は裏向きで数字がわかりません。
この状態から高橋君が勝つ確率を求める問題です。
カードの総枚数はわかりますので表向きのカードの分をひいて残りのカードの枚数を求めます。
裏向きのカードの数字が違う場合と同じ場合の2つにわけて考えます。
それぞれに配られたカードが1～9の範囲で全探索します。
残りのカード枚数がわかっているので、存在しないカードを配る場合は除外します。
カードが配られたらスコアを比較し、高橋君が勝つなら その場合の数を足していきます。
配られるカードが違うとき、数字i のカードの枚数に数字j の枚数をかけた値が勝つ場合の数になります。
同じときは、数字iのカード枚数と そこから1引いた枚数をかけた値が求める場合の数です。
この探索を終えると高橋君が勝つ場合の数が求まりますので、すべての場合の数で割った値が求める確率となります。
頭の中で整理してからコードを書き始めないと迷走してしまう気がする問題だと思ました。
量をこなしてバグが少ないコードが書けるよう精進したいです。
ABC193の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
