AtCoder Beginner Contest 201 C - Secret Number 【Python】
https://atcoder.jp/contests/abc201/tasks/abc201_c
AtCoder ProblemsのRecommendationで Difficulty: 439、Solve Probability: 48%でした。
解けませんでした。
公式解説
https://atcoder.jp/contests/abc201/editorial/1825
の暗証番号を全探索するという発想は全くありませんでした。
場合分けで解こうとしましたがそれぞれ何通りあるかの計算がわかりませんでした。
以下はユーザ解説
https://blog.hamayanhamayan.com/entry/2021/05/15/235640
の実装をそのままpythonで実装しただけです。
import math # https://note.nkmk.me/python-math-factorial-permutations-combinations/ def permutations_count(n, r): return math.factorial(n) // math.factorial(n - r) def combinations_count(n, r): return math.factorial(n) // (math.factorial(n - r) * math.factorial(r)) S = input() o_count = S.count('o') x_count = S.count('x') q_count = S.count('?') if o_count > 4 or o_count + q_count < 1: print(0) else: ans = 0 for add in range(q_count+1): if 0 < (o_count + add) <= 4: cnt = o_count + add if cnt == 1: ans += 1 * combinations_count(q_count, add) elif cnt == 2: ans += (2 * 4 + combinations_count(4, 2)) * combinations_count(q_count, add) elif cnt == 3: ans += 3 * 4 * 3 * combinations_count(q_count, add) elif cnt == 4: ans += permutations_count(4, 4) * combinations_count(q_count, add) print(ans)
同じものを含む順列や組み合わせについて検索しながら解説を読みました。
数学の勉強になりました。