はまやんはまやんはまやん

hamayanhamayan's blog

Just K [モノグサプログラミングコンテスト2022(AtCoder Beginner Contest 249) C]

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;
}