概要

この問題は、与えられた失敗条件を回避しながら、いくつかの料理を適切な順番で作り、得られる満足度の合計を最大化する問題です。料理の数 \(N\) が最大で \(19\) と非常に小さいことから、ビットDP（Bit DP） と 高速ゼータ変換（SOS DP） を用いることで、制限時間内に高速かつ正確に解くことができます。

---

考察

1. 素朴なアプローチとその限界

料理を作る順番をすべて探索すると、最悪で \(N!\) 通りの順序が存在します。\(N = 19\) のとき、\(19! \approx 1.2 \times 10^{17}\) となり、全探索では到底実行時間制限に間に合いません。

2. 状態の圧縮（順序から集合へ）

料理 \(p\) を作れるかどうかを決定する失敗条件 \((p, S)\) は、「料理 \(p\) を作り始める時点で、集合 \(S\) に含まれるすべての料理がすでに完成していること」です。 ここで重要なのは、「これまでにどの料理を作ったか」という集合のみが重要であり、「どのような順番で作ってきたか」は関係ないという点です。

したがって、料理の「順序」ではなく「これまでに完成させた料理の集合」を状態として管理するビットDPが有効です。集合は \(2^N\) 通り（\(N=19\) のとき \(524,288\) 通り）しかないため、十分に高速に処理できます。

3. 失敗条件の高速な判定（高速ゼータ変換の導入）

ある料理の集合 \(T\) がすでに完成しているとき、次に料理 \(p\) を作れるかを判定することを考えます。 失敗条件に引っかかるのは、ある失敗条件 \((p, S)\) が存在して、\(S \subseteq T\)（\(S\) が \(T\) の部分集合）となるときです。

これを素直に判定しようとすると、各状態 \(T\) においてすべての失敗条件をチェックする必要があり、計算量が爆大になってしまいます。 そこで、「すでに完成した料理の集合が \(T\) であるときに、作ることができない料理の集合」を bad[T]（ビットマスク）としてあらかじめ計算しておくことを考えます。

• 初期状態として、各失敗条件 \((p, S)\) について、bad[S] の \(p\) 番目のビットを \(1\) にします。
• もし \(S \subseteq T\) であれば、当然 \(T\) が完成しているときも料理 \(p\) は作れません。したがって、すべての \(S \subseteq T\) について、bad[S] の情報を bad[T] にマージ（論理和 |）する必要があります。

これは、超集合（Superset）方向への値の伝播に相当します。この伝播を愚直に行うと \(O(3^N)\) かかりますが、高速ゼータ変換（SOS DP）を用いることで \(O(N \cdot 2^N)\) で高速に行うことができます。

---

アルゴリズム

具体的な手順は以下の通りです。

Step 1: 失敗条件の初期化

各料理の番号を 0 から N-1 に変換（0-indexed）して処理します。 長さ \(2^N\) の配列 bad を \(0\) で初期化し、入力される各失敗条件 \((p, S)\) について、集合 \(S\) を表すビットマスク mask を作り、bad[mask] の \(p\) 番目のビットを \(1\) にします。

Step 2: 高速ゼータ変換（SOS DP）による失敗条件の伝播

以下の遷移により、すべての mask に対して、その部分集合の失敗条件をすべて累積します。

\[ \text{if } (mask \text{ の } i \text{ 番目のビットが } 1): \quad bad[mask] \leftarrow bad[mask] \lor bad[mask \setminus \{i\}] \]

これをすべての \(i \in [0, N-1]\)、すべての \(mask \in [0, 2^N-1]\) について順に行うことで、正しい bad テーブルが完成します。

Step 3: 各集合の満足度合計の事前計算

各集合 mask に含まれる料理の満足度の総和 sum_A[mask] を計算しておきます。 これは、mask から最も下位の立っているビット \(x\) を除いた集合の満足度合計に \(A_x\) を足すことで、\(O(1)\) で遷移でき、全体で \(O(2^N)\) で求められます。

Step 4: ビットDPによる探索

dp[mask] を「料理の集合 mask を、失敗条件に違反しない適切な順番で完成させることができるか」を表す真偽値（boolean）とします。

1. 初期化: dp[0] = true（何も作っていない状態は常に可能）、最大満足度 max_ans = 0。
2. 遷移: mask を \(0\) から \(2^N-1\) まで昇順にループします。
   • dp[mask] が false ならばスキップします。
   • dp[mask] が true ならば、現在の満足度 sum_A[mask] で max_ans を更新します。
   • 次に作ることができる料理の候補 next_candidates を求めます。
     • まだ作っていない料理：~mask
     • 現在の状況で作っても安全な料理：~bad[mask]
     • したがって、next_candidates = (~mask) & (~bad[mask]) となります（余計な上位ビットはマスクして消します）。
   • next_candidates でビットが立っている各料理 \(x\) について、dp[mask | (1 << x)] = true と更新します。

---

計算量

時間計算量

• 失敗条件の読み込み: \(O(M + \sum c_q)\)
• 高速ゼータ変換: \(O(N \cdot 2^N)\)
• 満足度の事前計算: \(O(2^N)\)
• DPの遷移: 各 mask について、次に遷移できる料理の候補（最大 \(N\) 個）を探索するため、 \(O(N \cdot 2^N)\)

全体としての時間計算量は \(O(M + \sum c_q + N \cdot 2^N)\) となります。 \(N = 19\) のとき \(N \cdot 2^N \approx 10^7\) 回の単純なビット演算であり、実行時間制限（通常 2.0 秒）に対して \(0.1\) 秒前後で非常に高速に動作します。

空間計算量

• bad, sum_A, dp の各配列のサイズが \(2^N\) です。

全体としての空間計算量は \(O(2^N)\) となります。 \(N = 19\) のとき、各配列に必要なメモリは数メガバイト程度であり、メモリ制限に対しても十分に余裕があります。

---

実装のポイント

1. __builtin_ctz による高速化

C++の組み込み関数 __builtin_ctz (Count Trailing Zeros) は、ビット列の右から（下位ビットから）連続する 0 の個数を数える関数です。 これを用いることで、ビットマスクの中で立っている最小のビットの位置を \(O(1)\) で取得できます。 * 満足度の事前計算時：int x = __builtin_ctz(mask); により、mask に含まれる料理を 1 つ高速に特定しています。 * DPの遷移時：next_candidates から料理 \(x\) を 1 つずつ取り出し、next_candidates ^= (1 << x) でそのビットを消していくことで、ビットが立っている位置のみを無駄なくループできます。

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // Optimize standard I/O operations for speed
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // bad[mask] stores a bitmask of dishes that cannot be cooked if 'mask' is the set of completed dishes.
    vector<int> bad(1 << N, 0);
    for (int i = 0; i < M; ++i) {
        int p, c;
        cin >> p >> c;
        --p; // Convert to 0-indexed
        int mask = 0;
        for (int j = 0; j < c; ++j) {
            int x;
            cin >> x;
            --x; // Convert to 0-indexed
            mask |= (1 << x);
        }
        bad[mask] |= (1 << p);
    }

    // Fast Zeta Transform (SOS DP) to propagate failure conditions to all supersets
    for (int i = 0; i < N; ++i) {
        for (int mask = 0; mask < (1 << N); ++mask) {
            if ((mask >> i) & 1) {
                bad[mask] |= bad[mask ^ (1 << i)];
            }
        }
    }

    // Precompute the sum of satisfaction for each subset of dishes
    vector<long long> sum_A(1 << N, 0);
    for (int mask = 1; mask < (1 << N); ++mask) {
        int x = __builtin_ctz(mask);
        sum_A[mask] = sum_A[mask ^ (1 << x)] + A[x];
    }

    // dp[mask] is true if the subset of dishes represented by 'mask' can be cooked in some valid order
    vector<bool> dp(1 << N, false);
    dp[0] = true;
    long long max_ans = 0; // Minimum satisfaction is 0 (by cooking 0 dishes)

    for (int mask = 0; mask < (1 << N); ++mask) {
        if (!dp[mask]) continue;
        max_ans = max(max_ans, sum_A[mask]);
        
        // Find candidates that are not yet cooked (~mask) and are safe to cook (~bad[mask])
        int next_candidates = (~mask) & (~bad[mask]) & ((1 << N) - 1);
        while (next_candidates > 0) {
            int x = __builtin_ctz(next_candidates);
            dp[mask | (1 << x)] = true;
            next_candidates ^= (1 << x);
        }
    }

    cout << max_ans << "\n";

    return 0;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。