Dangerous Chemicals [第五回 アルゴリズム実技検定 F]

https://atcoder.jp/contests/past202012-open/tasks/past202012_f

解説

https://atcoder.jp/contests/past202012-open/submissions/22284174

制約を見ると、薬品の混ぜ方が全探索できることが分かる。
これは薬品の混ぜ方は2¹⁴通りであるためである。
ビット全探索をして、全部の組み合わせを確かめる。

各薬品の混ぜ方について、条件をチェックしていこう。
O(2^N*M)は計算量的にはかなりギリギリなので、判定処理はかなり軽く行う必要がある。
必須でないかもしれないが、以下のような工夫を行う事でTLEを回避しよう。

ビットで扱う

配列ngのように爆発条件をビットで保持するように変換しておく。
そうすると、爆発するかどうかはmsk & ng[i]のようにANDをして、
ビットが3つ立っているかどうかで確認することができる。
一般にビット計算は軽い計算なので、軽い計算を目指すなら検討しよう。

ビットがいくつ立っているかの計算はbuiltin_popcountを利用することで軽く行う事ができる。
builtin_popcountは通常のビットを確認する方法よりも軽いアルゴリズムが使われている。
msbuildでは標準装備されてないので、注意。

ビットが2つ立っているならば、ビットが立っていないものが考慮すべき条件の薬品になるので、
記録しておこう。

あとは考慮すべき条件の薬品を数えて最大値を取ると答え。

int N, M, ABC[10101][3];
int ng[10101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        rep(j, 0, 3) cin >> ABC[i][j];
        rep(j, 0, 3) ABC[i][j]--;
        rep(j, 0, 3) ng[i] |= 1 << ABC[i][j];
    }
    

    int ans = 0;
    rep(msk, 0, 1 << N) {
        vector<bool> explosion(N);
        bool ok = true;
        rep(i, 0, M) {
            int an = msk & ng[i];
            if (__builtin_popcount(an) == 2) {
                rep(j, 0, 3) if (!(msk & (1 << ABC[i][j]))) explosion[ABC[i][j]] = true;
            }
            if (__builtin_popcount(an) == 3) ok = false;
        }
        if (ok) {
            int cnt = 0;
            rep(i, 0, N) if (explosion[i]) cnt++;
            chmax(ans, cnt);
        }
    }
    cout << ans << endl;
}