Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 289 C問題 Coverage

AtCoder ABC289 ABC 300 pts C問題

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$U:=\{1,2, \dots, N\}$ とする. $M$ 個の $U$ の部分集合 $S_1, \dots, S_M$ がある. ただし,

$S_i=\{a_{i,1}, \dots, a_{i,C_i} \}$

である.

このとき, $\mathcal{S}:=\{S_1, \dots, S_N \}$ の非空部分集合 $\mathcal{T} \subset \mathcal{S}$ のうち,

$\displaystyle \bigcup_{T \in \mathcal{T}} T=U$

となるのはいくつか?

制約

$1 \leq N \leq 10$
$1 \leq M \leq 10$
$1 \leq C_i \leq N$
$1 \leq a_{i,1} \lt \dots \lt a_{i,C_i} \leq N$

解法

一般的に, $K$ 要素の集合における非空部分集合の個数は $(2^K-1)$ 個である. よって, $\mathcal{S}$ の非空部分集合の個数は $(2^M-1)$ 個である. 今, $N,M \leq 10$ という制約から, この部分集合は全て列挙可能である.

よって, 各 $\mathcal{S}$ の非空部分集合 $\mathcal{T}$ に対して,

$\displaystyle \bigcup_{T \in \mathcal{T}} T=U$

であるかどうかは $O(NM)$ 時間で判定できる. そして, この等式が成り立つ $\mathcal{T}$ の数を求めれば良い.

従って, 合計 $O(2^M NM)$ 時間で求めることができた.