マイナビプログラミングコンテスト2021 C - Secret Number【Python解答例】

f:id:ebisuke33:20210516003234p:plain

マイナビプログラミングコンテスト2021(AtCoder Beginner Contest201)のC問題についてPythonの解答例を記事にしていきます。
Mynavi Programming Contest 2021（AtCoder Beginner Contest 201） - AtCoder

AtCoder Beginner Contest201 C - Secret Number

C - Secret Number

問題文

高橋くんは、暗証番号を忘れてしまいました。暗証番号は 0 から 9 までの数字のみからなる 4 桁の文字列で、0 から始まる場合もあります。
0 から 9 までの各数字について、高橋くんは以下のように記憶しています。彼の記憶は長さ 10 の文字列 S0S1…S9 によって表されます。

・Si が o のとき : 数字 i は暗証番号に確実に含まれていた。
・Si が x のとき : 数字 i は暗証番号に確実に含まれていなかった。
・Si が ? のとき : 数字 i が暗証番号に含まれているか分からない。
高橋くんが忘れてしまった暗証番号としてあり得るものは何通りありますか？

制約

・S は o, x, ? のみからなる長さ 10 の文字列

解答例

s = input()

# 確実に含まれていた数字の配列
OK = []
# 確実に含まれていない数字
NG = []

for i in range(10):
    if s[i] == "o":
        OK.append(i)
    elif s[i] == "x":
        NG.append(i)

# 答え
ans = 0

# 確実に使う数字が5個以上なら答えは存在しない
if len(OK) > 5:
    ans = 0
# 確実に使う数字が4個なら24通り
elif len(OK) == 4:
    ans = 4*3*2
else:
    # 0から9999まで全探索
    for i in range(10000):
        tmp = str(i)
        # 0を0000のように変換
        while len(tmp) < 4:
            tmp = "0" + tmp
        # tmpに含まれるOKの数字の数
        num = 0
        # 確実に使わない数字があるか判別
        flag = True
        for a in range(4):
            if int(tmp[a]) in NG:
                    flag = False
                
        # OKがtmpに含まれているか判別
        for j in range(len(OK)):
            # tmpの各桁を確認
            for k in range(4):
                if OK[j] == int(tmp[k]):
                    num += 1
                    break
        # 条件を満たせばans + 1
        if flag and num >= len(OK):
            ans += 1

print(ans)