ABC190 C問題

C - Bowls and Dishes

要約

頭ではなんとな〜くやり方が分かるんだけど実装に至るのが困難な問題．

多分今までだったら途中で諦めていたがなんとか無い頭をふり絞ってACを通すことができた．K人の人がどちらかの皿に置くか置かないかの２通りで，全部で2^K通りを試せば良い．そこからの実装にいつも苦しむが，前回学んだ"bit全探索"を使えばうまくできる．

解法

まず，入力が多いのでどうまとめるかを考える．

今回は，

cond：玉を置く条件をリストのリストとして表現する変数

choice：K番目の人が置く玉の候補をリストのリストとして表現するリスト

cond = [] #条件を格納
for i in range(M):
 A, B = map(int, input().split())
 cond.append((A, B))
K = int(input())
choice = [] #どっちに置く
for i in range(K):
 C, D =  map(int, input().split())
 choice.append((C, D))

これにより例えば入力例1では，

cond = ((1,2), (1,3), (2,4), (3,4))
coice = ((1,2), (1,3), (2,3))

のようになる．

次に玉を置く候補の決め方だか，前回も紹介した

from itertools import product
for bit in product((True, False), repeat=K):

を用いる．これにより，False(0)なら皿C_iに起き，True(1)なら皿D_iに置くと決めることで全パターンを網羅できる．

-------------------------------------------------------------------------

残りのフローは以下のコードにコメントした通り．

重要な事としてはsaraという変数で玉が置かれる場所を記録し，

各条件に対して，条件の(1, 3)のような集合がsara集合の部分集合内に入っているかを調べることで条件を満たしているかの判別を行っている

from itertools import product

#------入力情報の取得----------
N, M = map(int, input().split())
cond = [] #条件を格納
for i in range(M):
 A, B = map(int, input().split())
 cond.append((A, B))
K = int(input())
choice = [] #どっちに置く
for i in range(K):
 C, D =  map(int, input().split())
 choice.append((C, D))

#------以下main処理----------
ans = 0
for bit in product((True, False), repeat=K):
 #--1ループで変化する変数の初期化--
 count = 0
 sara = set() #たまが置かれる場所を格納するリスト
 #--たまが置かれる場所を決定--
 for i in range(K):
   sara.add(c[i][bit[i]])
 #--条件を満たすかを調べる--
 for i in range(M):
   #部分集合内に入っているかで決定
   if set(cond[i]) <= sara:
     count += 1
 ans = max(ans, count)
print(ans)