난이도

Gold 5

인증

문제

Oh how the cows love their pizza! Even though they are picky, they do love variety, too. They order from the local pizza parlor that features T (1 <= T <= 20) different toppings in addition to a complete set of soft drinks and healthy salads.

The toppings are conveniently numbered 1..T so the cows can order by number. Your job is to calculate how many possible pizzas can be created given that some cows will not tolerate various combinations of toppings (e.g., some cows simply will not eat Anchovies or the combination of Mushrooms and Asparagus).

Given a set of N (1 <= N <= 52) constraints, figure out how many pizzas can be made using all possible combinations of the ingredients (which, of course, includes no ingredients at all). Each constraint is a set of numbers of size 1..T that lists the ingredients that disqualify a pizza from being considered.

A constraint like “5 3” means that no pizza can contain ingredient #5 and also ingredient #3. This means a pizza with ingredients 3, 5, and 6 will not be counted as acceptable.

입력

Line 1: Two space-separated integers: T and N Lines 2..N+1: Each line describes a constraint using space-separated integers. The first integer is the number of ingredients in the constraint, Z (1 <= Z <= T). The subsequent Z integers (which are unique) list the ingredient(s) whose combination disqualifies a pizza from consideration for the cows.

출력

Line 1: A single integer that is the total number of pizzas that can be created using the number of ingredients and constraints.

예제 입력

6 5
1 1
2 4 2
3 3 2 6
1 5
3 3 4 6

예제 출력

10

해설 및 후기

문제 풀이보단 문제를 제대로 이해하는 데 시간이 조금 걸렸다. 받을 수 있는 T가 적으므로, 모든 경우의 수에 대한 비트 합(1을 해당 재료가 들어갔다고 생각하고, 0 을 해당 재료가 들어가지 않았다고 생각했을 때) 리스트를 구하고, 각 constraint를 순회하며 비트 And를 통해 constraint mask와 결과가 같다면 불가능한 조합이므로 False처리한다. 이후 False처리되지 않은 리스트 요소의 개수를 count하여 답을 구한다.

제출 코드

import sys
t, n = map(int, sys.stdin.readline().rstrip().split())
cse = [[i, True] for i in range(2**t)]
cnt = 0
c = []
for i in range(n):
    tmp = list(map(int, sys.stdin.readline().rstrip().split()))[1:]
    tmpRes = 0
    for j in tmp:
        tmpRes += 2 ** (j-1)
    for j in range(len(cse)):
        if cse[j][1]:
            if cse[j][0] & tmpRes == tmpRes:
                cse[j][1] = False

for i in cse:
    if(i[1]):
        cnt += 1

print(cnt)