Kazun の競プロ記録

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

AtCoder Beginner Contest 249 C問題 Just K

AtCoder ABC ABC249 C問題 300 pts

問題

提出解答

問題の概要

英小文字からなる $N$ 個の文字列 $S_1, \dots, S_N$ がある.

$S_1, \dots, S_N$ の中から好きな個数を選び抜く. このとき, 「「選んだ文字列において, ちょうど $K$ 個の文字列にその英小文字が存在する」を満たす英小文字の個数」の最大値を求めよ.

制約

$1 \leq N \leq 15$
$1 \leq K \leq N$
$S_i$ は英小文字からなる非空文字列で, 全ての文字が異なる.
$S_i \neq S_j$

解法

$N$ 個の文字列からの取り出し方は $2^N$ 通りである. 今, $N \leq 15$ であるから, 全列挙可能である.

従って, 各取り出し方において, 条件を満たす英小文字の個数を求め, それらの最大値を求めれば良い.

計算量は英小文字の数を $\sigma$ と書くことにすると, $O(N 2^N \sigma)$ である.