AtCoder Beginner Contest 190 C問題

AtCoder Python

前書き

面接でライブコーディングをやったのですが、難しいですね。
人が見ている場面でコーディングをした経験がなく、緊張してしまって、頭が真っ白になってしまいました・・・。
挙げ句の果てには「コードちゃんと書いてたの！？」と言われてしまう羽目に。つら。
自分が情けないので、Atcoderの問題ちゃんと解こう。

解いた問題

難易度：茶色
時間：30分

まさか泥臭く解く問題とはおもわず、賢い解法を探すのに時間がかかってしまいました・・・。
ヒントは2≤N≤100,2≤M≤100,1≤K≤16なので2**16をしても、パターンは最大65536通り。
最大65536通りの選択した数値パターンから、最も多くの条件式に当てはまる数値パターンを探します。
M=100個の条件式に当てはめて、最大何個の条件式が成立するか。

65536*100 = 6553600通りなので、計算できる？
書いてみた。

atcoder.jp

import itertools
n, m = map(int, input().split())
AB = list(list(map(int, input().split())) for i in range(m))
k = int(input())
CD = list(list(map(int, input().split())) for i in range(k))

pattern = list(itertools.product(range(0,2), repeat=k))
lis = [[CD[j][l] for j,l in enumerate(p)] for p in pattern]
countLis = []
for l in lis:
  count = 0
  _lis = set(l)
  for ab in AB:
    if (ab[0] in _lis) and (ab[1] in _lis): 
      count+=1
  countLis.append(count)
print(max(countLis))

結果

AC。いけた。