概要

\(N\) 種類の料理を、失敗条件に抵触しないような実行可能な順序でいくつか作り、得られる満足度の合計を最大化する問題です。 \(N \le 19\) という制約に着目し、ビットDP（Bit DP）と高速ゼータ変換（SOS DP）を組み合わせることで、制限時間内に高速に解くことができます。

考察

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

料理を作る順番をすべて試す素朴な方法（順列の全探索）では、計算量が \(O(N!)\) となり、\(N=19\) では \(19! \approx 1.2 \times 10^{17}\) のため実行不可能です。

また、すでに作った料理の集合を \(U\) としたとき、次に作ることができる料理 \(p \notin U\) を判定することを考えます。 料理 \(p\) を作れない（失敗する）のは、ある失敗条件 \((p, S)\) が存在して \(S \subseteq U\) となっているときです。 これを愚直に判定しようとすると、各状態 \(U\)（\(2^N\) 通り）に対して、すべての失敗条件 \(M\) 個をチェックする必要があり、計算量が \(O(M 2^N)\) となってしまいます。\(10^5 \times 5 \times 10^5 \approx 5 \times 10^{10}\) 回の演算が必要になり、これも実行時間制限に間に合いません。

解決へのアプローチ：高速ゼータ変換の利用

この問題を解決するために、「すでに作った料理の集合 \(U\) が与えられたとき、次に作ることができない料理の集合 \(F(U)\)」を事前に一括で高速に計算しておくことを考えます。

定義より、集合 \(U\) に対して禁止される料理の集合 \(F(U)\) は、以下のように表せます。 $\(F(U) = \bigcup_{S \subseteq U} \{ p \mid (p, S) \text{ は失敗条件} \}\)$

これは、各 \(S\) について「直接的に禁止される料理の集合」（これを forbidden[S] とします）を初期値として、部分集合の和（OR）を求める問題に帰着されます。 $\(F(U) = \bigcup_{S \subseteq U} \text{forbidden}[S]\)$

この形の計算は、高速ゼータ変換（SOS DP: Sum Over Subsets DP）を用いることで、すべての \(U\) について \(O(N 2^N)\) で一括して求めることができます。 これが求まれば、集合 \(U\) の状態から次に作ることができる料理は、 - まだ作っていない料理（\(\notin U\)） - かつ、禁止されていない料理（\(\notin F(U)\)） となり、ビット演算を用いて \(O(1)\) で判定・遷移できるようになります。

---

アルゴリズム

1. 失敗条件の初期化

長さ \(2^N\) の配列 forbidden を用意します。 各失敗条件 \((p, S)\) について、forbidden[S] の \(p\) 番目のビットを \(1\) にします。

2. 高速ゼータ変換による禁止集合の伝播

高速ゼータ変換を行い、すべての \(U\) に対して \(F(U) = \bigcup_{S \subseteq U} \text{forbidden}[S]\) を計算します。 具体的には、各次元（料理 \(i = 0, \dots, N-1\)）について、料理 \(i\) を含まない集合 sub の値を、料理 \(i\) を含む集合 sub + (1 << i) に OR 演算で足し合わせていきます。

3. 各集合の満足度の総和の計算

同様に、各集合 \(U\) を作ったときに得られる満足度の総和 A_sum[U] を高速ゼータ変換（こちらは加算）を用いて \(O(N 2^N)\) で事前に計算しておきます。

4. ビットDPによる最大値の探索

dp[mask] を「料理の集合 mask を実行可能な順序で完成させることが可能か（True/False）」とするDPを行います。

• 初期値: dp[0] = True
• 遷移: dp[mask] が True であるとき、次に作ることができる料理の候補 valid を以下のようにビット演算で求めます。 valid = all_mask & ~(forbidden[mask] | mask) （全体集合から、「すでに作った料理 mask」と「現在禁止されている料理 forbidden[mask]」を除外したもの）
• valid に含まれる各料理 \(p\) について、dp[mask | (1 << p)] = True と更新します。
• dp[mask] が True であるすべての mask について、A_sum[mask] の最大値を答えとします。

---

計算量

• 時間計算量: \(O(N 2^N + M)\)

  • 失敗条件の入力と初期化: \(O(M)\)
  • forbidden の高速ゼータ変換: \(O(N 2^N)\)
  • A_sum の高速ゼータ変換: \(O(N 2^N)\)
  • DPの遷移: 各 mask について、次に遷移可能な料理の個数（最大 \(N\) 個）だけループが回るため、最悪でも \(O(N 2^N)\) です。
  • \(N = 19\) のとき、\(N 2^N \approx 19 \times 5.2 \times 10^5 \approx 10^7\) となり、Pythonでも十分に高速に動作します。

• 空間計算量: \(O(2^N)\)

  • forbidden, A_sum, dp の各配列のサイズは \(2^N\) です。
  • \(N = 19\) のとき \(2^{19} = 524,288\) 要素であり、メモリ消費量は数MB〜数十MB程度に収まり、メモリ制限に対して非常に安全です。

---

実装 of ポイント

• ビット演算による高速化: DPの遷移において、valid に立っているビット（次に作れる料理）を列挙する際、p = valid & -valid（最も右にある立っているビットを抽出するトリック）と valid ^= p を用いることで、立っているビットの数（= 遷移先の数）だけのループで高速に処理しています。

• 1-indexed から 0-indexed への変換: 入力される料理の番号は \(1\) から \(N\) ですが、ビット演算をスムーズに行うために、コード内では \(0\) から \(N-1\) にデクリメントして処理しています。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    M = int(input_data[1])
    A = [int(x) for x in input_data[2:2+N]]
    
    forbidden = [0] * (1 << N)
    
    idx = 2 + N
    for _ in range(M):
        p = int(input_data[idx]) - 1
        c = int(input_data[idx+1])
        mask_S = 0
        for j in range(c):
            mask_S |= 1 << (int(input_data[idx+2+j]) - 1)
        forbidden[mask_S] |= 1 << p
        idx += 2 + c
        
    # 高速ゼータ変換 (Superset OR)
    for i in range(N):
        bit = 1 << i
        for mask in range(0, 1 << N, bit << 1):
            for sub in range(mask, mask + bit):
                forbidden[sub + bit] |= forbidden[sub]
                
    # A_sum の計算
    A_sum = [0] * (1 << N)
    for i in range(N):
        bit = 1 << i
        val = A[i]
        for mask in range(0, 1 << N, bit << 1):
            for sub in range(mask, mask + bit):
                A_sum[sub + bit] = A_sum[sub] + val
                
    # DP
    dp = [False] * (1 << N)
    dp[0] = True
    ans = 0
    
    all_mask = (1 << N) - 1
    for mask in range(1 << N):
        if not dp[mask]:
            continue
        if A_sum[mask] > ans:
            ans = A_sum[mask]
        
        valid = all_mask & ~(forbidden[mask] | mask)
        while valid:
            p = valid & -valid
            dp[mask | p] = True
            valid ^= p
            
    print(ans)

if __name__ == '__main__':
    solve()

---

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