ABC190 C - Bowls and Dishes から学んだ

とりあえず、全探索で思いつくまま書いた。

BowlsAndDishes_r1.py

N,M = map(int,input().split())
dish = []

for i in range(M):
    a,b = map(int,input().split())
    dish.append([a,b])

K = int(input())
lis = []
for _ in range(K):
    c,d = map(int,input().split())
    lis.append([c,d])

from itertools import product
ans = 0
for x in product([0,1],repeat=K):
    nums = []
    cnt = 0
    x = list(x)
    #print(x)
    for k in range(K):
        nums.append(lis[k][x[k]])
    nums = set(nums)#<= ココをlist にすると確実に TLE になるので注意
    for a,b in dish:
        if a in nums and b in nums:
            cnt +=1
        ans = max(ans,cnt)
print(ans)

ビット全探索を使ってみた。
ただ、これでも TLE となったが、こんな感じだった。

TLE でコケルときって、もっと沢山こけるべ。
じゃあ、pypy + def の合わせ技でどうだべ。

BowlsAndDishes_r2.py

def solv():
    N,M = map(int,input().split())
    dish = []

    for i in range(M):
        a,b = map(int,input().split())
        dish.append([a,b])

    K = int(input())
    lis = []
    for _ in range(K):
        c,d = map(int,input().split())
        lis.append([c,d])

    from itertools import product
    ans = 0
    for x in product([0,1],repeat=K):
        nums = []
        cnt = 0
        x = list(x)
        for k in range(K):
            nums.append(lis[k][x[k]])
        nums = set(nums)

        for a,b in dish:
            if a in nums and b in nums:
                cnt +=1
        ans = max(ans,cnt)
    print(ans)

solv()

通った。

---

過去の記述は忘れた状態で再チャレンジ。
K 人が置いた組み合わせは True or False として
memo することにした。

あとは両方のお皿において True になっている組み合わせを
カウントするだけ。

abc190c.py

N,M = map(int,input().split())
dish = []
for _ in range(M):
    a,b = map(int,input().split())
    dish.append([a,b])
K = int(input())
select = []
for _ in range(K):
    c,d = map(int,input().split())
    select.append([c,d])

ans = 0
from itertools import product
for num in product([0,1],repeat=K):#O(2^K)
    num = list(num)
    memo = [False] * 101
    cnt = 0
    for i in range(K):#O(K)
        memo[select[i][num[i]]] = True
    for j in range(M):#O(M)
        if memo[dish[j][0]] and memo[dish[j][1]]:
            cnt += 1
    ans = max(ans,cnt)
print(ans)
#O(2^K*(K+M))

これなら 10^6 オーダーなので python でも
普通に間に合う。