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)