AtCoder Beginner Contest 190 C - Bowls and Dishes 【Python】

https://atcoder.jp/contests/abc190/tasks/abc190_c

AtCoder ProblemsのRecommendationで Difficulty: 472、Solve Probability: 44%でした。

Kの制約が16で2つの皿のどちらかにボールを置くとのことなので、bit全探索で置かれた皿をsetで管理することで解くことができました。

bit全探索はアルゴリズム実技検定公式テキスト
https://github.com/kenkoooo/pastbook-source-code/blob/27e3c52d4ea895cd8ae6407fe4e48dc81f4c6f28/chukyu/python/chapter06/section05/6-5-1.py
のコードを参考にしました。

N, M = map(int, input().split())
C = []
for i in range(M):
    a, b = map(int, input().split())
    C.append([a-1, b-1])
K = int(input())
D = []
for i in range(K):
    c, d = map(int, input().split())
    D.append([c-1, d-1])

# 集合としてあり得るものの個数
ALL = 1<<K

# 集合ごとに、ボールが置かれた皿をセットで管理する
B = []
for i in range(ALL):
    B.append(set())

# n で表現される集合に要素 i が含まれるかを判定して True/False を返す関数
def has_bit(n, i):
    return (n & (1<<i) > 0)

# 集合ごとに、ボールが置かれた皿を前もって求める
for n in range(ALL):
    for i in range(K):
        c, d = D[i]
        if has_bit(n, i):
            B[n].add(c)
        else:
            B[n].add(d)

# 満たされる条件の個数の最大を求める
ans = 0
for n in range(ALL):
    num = 0
    for i in range(M):
        a, b = C[i]
        if a in B[n] and b in B[n]:
            num += 1
    ans = max(ans, num)
print(ans)