概要

\(N\) 種類の料理からいくつかを選び、失敗条件（「料理 \(p\) を作る前に集合 \(S\) が完成していると失敗する」）に抵触しないような順番で料理を作ったときの、満足度の合計の最大値を求める問題です。

料理の数 \(N\) が最大 19 と小さいため、ビット DP（集合 DP） を用いて解くことができます。

考察

1. 順序と集合の分離

一見すると「どのような順番で作るか」という順列の全探索（\(N!\) 通り）が必要そうに見えます。しかし、ある料理の集合 \(M\) が「実行可能」であるとは、「集合 \(M\) に含まれる料理をうまく並べて、一度も失敗条件に該当せずに作り終えることができる」 ということと同義です。

一度ある集合 \(M\) が実行可能であると分かれば、その満足度の合計は料理を出す順番に依存せず \(\sum_{i \in M} A_i\) と定まります。したがって、「どの料理の集合が実行可能か」を判定することに注力すればよいです。

2. 失敗条件の効率的な管理

失敗条件 \((p, S)\) は、「料理 \(p\) を作る直前に、すでに完成している料理の集合 \(mask\) が \(S \subseteq mask\) を満たしていると、料理 \(p\) は作れない」と言い換えられます。

各 \(mask\) に対して、「その時点で次に作ることができない料理の集合」を bad_mask[mask] として管理したいです。 - 初期状態：各失敗条件 \((p, S)\) について、bad_mask[S] の \(p\) 番目のビットを立てる。 - 伝搬：もし集合 \(S\) で料理 \(p\) が作れないなら、\(S\) を含むより大きな集合 \(S' \supseteq S\) でも当然料理 \(p\) は作れません。

これを素直に計算すると時間がかかりますが、SOS DP (Sum Over Subsets) の要領で \(O(N 2^N)\) で全ての \(mask\) に対する不可な料理を列挙できます。

3. 実行可能性の判定 (Bit DP)

ある集合 \(mask\) が実行可能かどうかを判定します。 - reachable[mask] を「集合 \(mask\) に含まれる料理をある順序で全て完成させることが可能か」という真偽値とします。 - reachable[0] = true（何も作らない状態は常に可能） - reachable[mask] が真になる条件： ある料理 \(p \in mask\) が存在して、以下の 2 つを同時に満たすこと。 1. reachable[mask \setminus \{p\}] が真である（\(p\) 以外の料理を先に完成させられる）。 2. 集合 \(mask \setminus \{p\}\) が完成している状態で、料理 \(p\) の失敗条件に該当しない。

アルゴリズム

1. 失敗条件の整理: 各失敗条件 \((p, S)\) をビットマスクで持ちます。bad_mask[S] に \(p\) を記録します。
2. SOS DP による伝搬: 「\(S\) でダメなら \(S\) の超集合でもダメ」という情報を更新します。

   
   for i in range(N):
       for mask in range(1 << N):
           if mask & (1 << i):
               bad_mask[mask] |= bad_mask[mask ^ (1 << i)]
   

3. 満足度の前計算: 各 mask に対応する満足度の総和 satisfaction[mask] を計算しておきます（\(O(2^N)\)）。
4. 実行可能性の DP: mask を \(1\) から \(2^N-1\) まで走査し、上述の判定式に基づき reachable[mask] を埋めます。reachable[mask] が真になるたびに、ans = max(ans, satisfaction[mask]) を更新します。

計算量

• 時間計算量: \(O(M + N 2^N)\)
  • 失敗条件の入力に \(O(M + \sum c_q)\)。
  • SOS DP 部分に \(O(N 2^N)\)。
  • Reachability DP 部分に \(O(N 2^N)\)。
  • \(N=19\) のとき \(N 2^N \approx 10^7\) なので、制限時間内に十分間に合います。
• 空間計算量: \(O(2^N)\)
  • bad_mask, satisfaction, reachable の各配列で \(2^N\) のメモリを使用します。

実装のポイント

• ビット演算の活用: mask \setminus \{p\} は mask ^ (1 << p) で計算できます。また、mask 内の立っているビットを順に調べる際は while m: p_bit = m & -m; m &= m - 1 のようなテクニックを使うと高速です。

• 早期打ち切り: reachable[mask] を判定する際、1 つでも条件を満たす料理 \(p\) が見つかればその時点で break して次の mask の計算に移ることで定数倍の高速化が期待できます。

• メモリ節約: Python の場合、reachable 配列を bytearray にすることでメモリ使用量を抑えることができます。

  ソースコード

import sys

def solve():
    # Use fast I/O by reading all at once and using an iterator
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    N = int(next(it))
    M = int(next(it))
    
    # Satisfaction values for each dish
    A = [int(next(it)) for _ in range(N)]
    
    # bad_mask[mask] has the p-th bit set if dish p cannot be completed 
    # if the set of dishes already finished is 'mask'.
    # A dish p is disqualified if any of its failure conditions (p, S) satisfy S ⊆ mask.
    bad_mask = [0] * (1 << N)
    for _ in range(M):
        p = int(next(it)) - 1
        c = int(next(it))
        S_mask = 0
        for _ in range(c):
            S_mask |= (1 << (int(next(it)) - 1))
        # Initially, mark that dish p is bad if exactly S_mask is completed.
        bad_mask[S_mask] |= (1 << p)
    
    # SOS DP (Sum Over Subsets) to propagate the failure conditions.
    # If dish p is bad for a subset S, it is also bad for any superset of S.
    # Time Complexity: O(N * 2^N)
    for i in range(N):
        bit = 1 << i
        for mask in range(1 << N):
            if mask & bit:
                bad_mask[mask] |= bad_mask[mask ^ bit]
    
    # satisfaction[mask] stores the total satisfaction of dishes represented by the mask.
    # Time Complexity: O(2^N)
    satisfaction = [0] * (1 << N)
    for i in range(N):
        bit = 1 << i
        a_i = A[i]
        for mask in range(bit):
            satisfaction[mask | bit] = satisfaction[mask] + a_i
            
    # reachable[mask] is 1 if there exists at least one executable sequence
    # using exactly the set of dishes represented by 'mask'.
    reachable = bytearray(1 << N)
    reachable[0] = 1 # Empty sequence is always executable
    
    # Precompute bit to index mapping for powers of 2 to speed up the main loop.
    bit_to_idx = [0] * (1 << N)
    for i in range(N):
        bit_to_idx[1 << i] = i
    
    ans = 0
    # Main DP to determine reachable subsets and find the maximum satisfaction.
    # A set 'mask' is reachable if there is some dish p in 'mask' such that
    # 'mask \ {p}' was reachable and dish p could be added after 'mask \ {p}'.
    # Time Complexity: O(N * 2^N) with early exit.
    for mask in range(1, 1 << N):
        m = mask
        while m:
            # Extract the lowest set bit (representing a potential last dish p)
            p_bit = m & -m
            prev_m = mask ^ p_bit
            
            # If the subset without dish p was reachable, check the failure condition for p.
            if reachable[prev_m]:
                # Dish p is valid to add if no failure condition (p, S) has S ⊆ prev_m.
                if not (bad_mask[prev_m] & p_bit):
                    reachable[mask] = 1
                    # Update global maximum satisfaction if this subset is reachable.
                    if satisfaction[mask] > ans:
                        ans = satisfaction[mask]
                    # Once a mask is proven reachable, no need to check other dishes.
                    break
            
            # Clear the lowest set bit to check the next dish in the mask.
            m &= m - 1
    
    # Output the maximum satisfaction found among all reachable sequences.
    sys.stdout.write(str(ans) + '\n')

if __name__ == '__main__':
    solve()

---

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