問題概要

ポップコーンには $M$ 種類の味 $1, 2, \dots, M$ がある。

一方、ポップコーンを得る $N$ 個の店 $1, 2, \dots, N$ がある。各店 $i$ でどの味のポップコーンを売っているかを表す文字列 $S_{i}$ が与えられる。文字 $S_{i, j}$ が 'o' であるとき、店 $i$ で味 $j$ を売っていることを表し、'x' であるときは売っていないことを表す。

なお、どの味のポップコーンも、いずれかの店で売られることが保証されている。

すべての味のポップコーンを買い揃えるためには、最小で何個の店で買い物すればよいかを求めよ。

制約

$1 \le N, M \le 10$

考えたこと

店の選び方は、店ごとに「買い物する」「買い物しない」という 2 通りずつの選択肢があるので、 $2^{N}$ 通りある。このような $2^{N}$ 通りの選択をすべて調べ上げる方法としてビット全探索がある。ビット全探索については、次の記事を参照。

drken1215.hatenablog.com

買い物する店を決めたときに、それがすべてのポップコーンを揃えられるかを判定し、揃えられる場合についての、店の個数の最小値を求めれば良い。

計算量は $O(2^{N}M)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<string> S(N);
    for (int i = 0; i < N; ++i) cin >> S[i];
    
    int res = N;
    for (int bit = 0; bit < (1 << N); ++bit) {
        vector<bool> hihuku(M, false);
        for (int i = 0; i < N; ++i) {
            if (!(bit & (1 << i))) continue;
            for (int j = 0; j < M; ++j) {
                if (S[i][j] == 'o') hihuku[j] = true;
            }
        }
        bool ok = true;
        for (int j = 0; j < M; ++j) if (!hihuku[j]) ok = false;
        
        if (ok) res = min(res, __builtin_popcount(bit));
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 358 C - Popcorn (3Q, 灰色, 300 点)

問題概要

制約

考えたこと

コード