소스 코드

import sys
from itertools import combinations
input = sys.stdin.readline

def convert_word_to_bit(word):
    converted_bit = 0b0
    for c in word:
        converted_bit |= 1 << (ord(c) - 96)

    return converted_bit

def is_readable(word_bit, candidate_bit):
    return (word_bit | candidate_bit) <= candidate_bit

def solution(K, base_bit):
    if K < 5:
        return 0
    
    K_rest = K - 5
    result = 0

    for locs in combinations(set(range(1, 27)) - base_loc, K_rest):
        candidate_bit = base_bit
        
        for loc in locs:
            candidate_bit |= 1 << loc

        count = 0
        for word in words:
            word_bit = convert_word_to_bit(word)

            if is_readable(word_bit, candidate_bit):
                count += 1
        
        result = max(result, count)
    
    return result


N, K = map(int, input().rstrip().split())
words = [input().rstrip() for _ in range(N)]

base_bit = 0b0
base_loc = set()
for c in "antic":
    bit_loc = ord(c) - 96
    base_loc.add(bit_loc)
    base_bit |= 1 << bit_loc

print(solution(K, base_bit))

풀이 요약 (pypy3 통과)

1. 모든 단어는 anta로 시작하고, tica로 끝난다. 즉, "a n t i c" 요 5글자는 반드시 가르쳐야만 한다. 즉 K가 5 미만이라면 어떤 단어도 읽을 수 없다.

2. K가 5 이상이라면 문제의 조건을 고려하여 정답값을 알아내야한다. 여기선 비트마스킹을 활용했다.

   우선 a n t i c 를 비트마스킹하여 base_bit에 저장해둔다.

3. K_rest에 a n t i c 5개를 제외한 나머지 가르칠 수 있는 글자 개수를 기록해둔다.

   그리고 a n t i c를 제외한 21개의 글자 중에서 K_rest 만큼을 조합으로 뽑는다. (이 때, 뽑는 수는 1~26의 숫자들이 대상이고, 해당 숫자는 비트 마스킹에서의 위치(2의 지수)를 의미한다)

4. 뽑은 글자 후보를 base_bit 비트마스킹에 반영하여 candidate_bit를 구하고, 이 것을 주어진 모든 남극 단어들과 비교하면서 읽을 수 있는 단어를 카운팅하고, 그 것을 result에 최대값을 계속 갱신하면서 결과값을 찾아나간다.

어려웠던 점, 배운 점

처음에 이 풀이와 유사한 로직을 생각했을 때는, 시간복잡도를 계산할 때 $_{26}C_{13}$ x 50 으로 계산을 해버려서 TLE가 난다고 생각해서 이렇게는 못 풀겠다고 생각해서 결국 다른 사람 풀이를 참고했는데, 알고보니 26개가 아닌 필수인 5개를 뺀 21개를 대상으로 조합을 생각했어야 했다.

근데 그걸 고려해도 python으로 제출하면 TLE가 나고 pypy3로 제출하면 통과한다. 좀 더 최적화를 해야되겠지만 일단 비트마스킹은 가볍게 보고 넘기기로 했으니 여기까지만..