https://atcoder.jp/contests/abc249/tasks/abc249_c
前提知識
- bit全列挙
解説
https://atcoder.jp/contests/abc249/submissions/31208645
この問題ではbit全列挙が分かっているとスムーズに解くことができる。
bit全列挙については、他に詳しい解説があるので、そちらを参照して学習することをすすめる。
全列挙
競技プログラミングの基本は全列挙である。
今回、文字列を好きな個数選ぶことができるということであるが、Nがとても小さいので、
その文字列の選び方を全て列挙して検証することができる。
今回のような、選ぶ選ばないというのを全列挙するのに使えるのがbit全列挙である。
bitの01を選ぶ選ばないにマッピングすることで選択状態をbit列、ないし、数値として考えることができる。
全列挙するにあたってbit全列挙を使うことは必須ではないのだが、とてもお手軽な書き方であるし、
かつ、多くの解説がbit全列挙を前提に書いてあることが多いので、理解しておくといい。
とある選択方法について種類数を数える
全ての選択方法は列挙しても間に合うので、後はそれぞれの選び方について
『「選んだ文字列の中でちょうど K 個の文字列に登場する英小文字」の種類数』が計算できればいい。
これは全ての文字列に対して文字をカウントして、K個であるものを最後に数えればいい。
自分はmapを使って、
cnt[c] := 文字cが現れる回数
を選択した文字列に対して集計して、回数がK個である文字数を数えて、その最大値を取るようなコードを書いた。
int N, K; string S[15]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> K; rep(i, 0, N) cin >> S[i]; int ans = 0; rep(msk, 0, 1 << N) { map<char, int> cnt; rep(i, 0, N) if (msk & (1 << i)) fore(c, S[i]) cnt[c]++; int ok = 0; fore(p, cnt) if (p.second == K) ok++; chmax(ans, ok); } cout << ans << endl; }