ABC193 D Poker
裏向きのカードに書かれた数を高橋くん, 青木くんともに全探索することを考える(それぞれ今書かれていたと仮定した数を$ i, jとおく). まずスコア計算については各数字が何回出現したかを配列に保存しておくことによって実装できる. 本質部分である確率について考える. 以降, 同じ数のカードでも区別して考える. すると確率の分母にあたる全事象は, $ (9K - 8)(9K - 9)と表せる. また分子の計算は, 高橋くんについては操作前の$ iが書かれているカードの残り枚数$ cnt_iとなり, 青木くんについては高橋くんが操作を行った後の$ jが書かれているカードの残り枚数$ cnt_jとなるのでこれらをかけ合わせたものを足していくことによって求められる(詳しくは実装例を見ていただきたい).
よってこの問題を$ O(1)(高々カードの数は9通りしかない)で解くことができた.