初めに

atcoder.jp 解けなかったので

敗因

精選 150 問を解いています.

半分全列挙の問題というところはヒントとして知っていたけれど, 解法がよく分かりませんでした...

Unite 部分が難しくて解決方法がまったく思いつかなかった.

グラフ上で考えて $A_i$ と $B_i$ を辺でつなぐ. 最大独立集合は? と言い換える.

解説の図のように, ある部分集合を決めてしまえば, それを独立集合かどうか判定した上で, その集合に含まれる頂点と辺でつながれている頂点を除いたものの最大独立集合は? と言い換えられる.

この問題の本質は, 異なる部分集合 $S, \, T$ が存在して, 独立集合 $s \in S, \, t \in T$ が存在したとき, 集合 $s \cup t$ は, 集合 $S \cup T$ 内でも独立集合であるという性質による.

あとは, ある部分集合内での最大独立集合を求めておけばよくて, これは bitDP などで事前に計算しておくことができる.

$isok[s$ ] := $s ( \in V1 )$ が独立集合であるかどうか

$u[s$ ] := $s ( \in V1 )$ と辺でつながれていない頂点 $u_i ( \in V2 )$ の集合

$dp[u$ ] := $u ( \in V2 )$ の部分集合での最大独立集合のサイズ

バグらせまくりましたが...