質問リンク

1062-教訓

問題の説明

与えられたすべての単語N個は「anta」で始まり、「tica」で終わる.K文字からなる単語しか読み取れない場合は、Kを読み取り可能な最大単語数に設定します.読み取り可能な単語の最値を求めるプログラムを作成してください.

問題を解く

試行1

import sys
from collections import defaultdict
from itertools import combinations

input = sys.stdin.readline

N, K = map(int, input().split())
words = []
alph = set()
readable = ['a', 'n', 't', 'i', 'c']

for _ in range(N):
    words.append(list(input().strip()))
    # N개의 단어 중 ['a', 'n', 't', 'i', 'c']에 포함되지 않는 알파벳 저장
    for w in words[-1][4:-4]:
        if w not in readable:
            alph.add(w)

if K < 5:
    print(0)
    sys.exit(0)

K -= 5

# 읽어야 하는 단어가 K보다 작거나 같으면 모든 단어 읽을 수 있음
if len(alph) <= K:
    print(len(words))
    sys.exit(0)
else:
    pos = combinations(alph, K)

answer = 0
for p in pos:
    count = 0
    for word in words:
        flag = True
        for w in word[4:-4]:
            if w not in readable and w not in p:
                flag = False
                break
        if flag == True:
            count += 1
    answer = max(answer, count)

print(answer)

2ビットマスクを試します