概要

前提関係（循環を含みうる）を満たす研究テーマの部分集合を選び、利益（成果の価値 − 費用）の合計を最大化する問題です。\(N \leq 15\) という制約を活かし、全部分集合をビットマスクで列挙して解きます。

考察

問題の本質

研究テーマの集合 \(S\) を選ぶとき、「\(U_j \in S\) ならば \(V_j \in S\)」という制約をすべて満たす必要があります。これは、\(S\) が前提関係の有向グラフにおいて閉集合（closed set）であることを意味します。つまり、\(S\) に含まれるノードから出る辺の先もすべて \(S\) に含まれていなければなりません。

循環がある場合

前提関係に循環がある場合（例えば \(A \to B\) かつ \(B \to A\)）、\(A\) と \(B\) は「選ぶなら両方、選ばないなら両方」という関係になります。SCC（強連結成分分解）で縮約する方法もありますが、\(N \leq 15\) なので全列挙で十分です。

\(N \leq 15\) の意味

\(2^{15} = 32768\) なので、すべての部分集合を列挙しても十分高速です。各部分集合に対して「前提関係を満たすか？」を判定し、満たすものの中で利益が最大のものを求めればよいです。

有効性の判定を高速にするには

各ノード \(i\) について、\(i\) を選んだときに必ず選ばなければならないノードの集合をビットマスク \(\text{req}[i]\) で持ちます。部分集合 \(S\) が有効であるためには、\(S\) に含まれる全ノードの要求をまとめた \(\text{combined\_req}[S] = \bigcup_{i \in S} \text{req}[i]\) が \(S\) の部分集合である必要があります。

\(\text{combined\_req}\) はビットOR演算で増分的に計算できるので、各部分集合に対して \(O(1)\) で求められます。

アルゴリズム

1. 入力処理: 各ノード \(i\) の \(P_i, C_i\) と前提関係を読み込む。
2. 前提条件のビットマスク化: ノード \(i\) から辺が出ているノードの集合を \(\text{req}[i]\) としてビットマスクで管理。
3. 部分集合の利益の前計算: \(\text{subset\_val}[\text{mask}]\) を、最下位ビットを使った増分計算で \(O(1)\) ずつ求める。
   • \(\text{subset\_val}[\text{mask}] = \text{subset\_val}[\text{mask} \setminus \text{lsb}] + (P_{\text{bit}} - C_{\text{bit}})\)
4. 要求の合成の前計算: \(\text{combined\_req}[\text{mask}]\) も同様に増分計算。
   • \(\text{combined\_req}[\text{mask}] = \text{combined\_req}[\text{mask} \setminus \text{lsb}] \mid \text{req}[\text{bit}]\)
5. 全列挙と判定: 各 \(\text{mask}\) について、\((\text{combined\_req}[\text{mask}]\ \&\ \text{mask}) = \text{combined\_req}[\text{mask}]\) なら有効。有効な集合の中で \(\text{subset\_val}[\text{mask}]\) の最大値を求める。
6. 空集合（利益 \(0\)）も候補に含めるため、答えの初期値を \(0\) とする。

具体例

\(N=3\)、テーマ1→テーマ2 の前提関係があるとき： - \(\text{req}[0] = \{1\} = 010_2\)、\(\text{req}[1] = 0\)、\(\text{req}[2] = 0\) - \(S = \{1\}\)（\(= 001_2\)）→ \(\text{combined\_req} = 010_2\)、\(010_2 \& 001_2 = 000_2 \neq 010_2\) → 無効 - \(S = \{1, 2\}\)（\(= 011_2\)）→ \(\text{combined\_req} = 010_2\)、\(010_2 \& 011_2 = 010_2\) → 有効

計算量

• 時間計算量: \(O(2^N)\) — 全 \(2^N\) 個の部分集合を列挙し、各部分集合について \(O(1)\) で判定・計算
• 空間計算量: \(O(2^N)\) — \(\text{subset\_val}\) と \(\text{combined\_req}\) のテーブル

\(N \leq 15\) なので \(2^{15} = 32768\) であり、十分高速です。

実装のポイント

• 最下位ビット（LSB）の取得: lsb = mask & (-mask) で最下位の立っているビットを取得し、bit = lsb.bit_length() - 1 でそのビット位置を得る。これにより増分的な DP が可能。

• ビット演算による部分集合判定: 「\(A\) が \(B\) の部分集合か」は (A & B) == A で \(O(1)\) 判定できる。

• 答えの初期値を \(0\) にする: 空集合を選ぶ場合の利益が \(0\) なので、すべてのテーマが赤字でも \(0\) を返せるようにする。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    P = [0] * N
    C = [0] * N
    for i in range(N):
        P[i] = int(input_data[idx]); idx += 1
        C[i] = int(input_data[idx]); idx += 1
    
    # For each node i, req[i] is a bitmask of nodes that must also be in S if i is in S
    req = [0] * N
    for j in range(M):
        u = int(input_data[idx]) - 1; idx += 1
        v = int(input_data[idx]) - 1; idx += 1
        req[u] |= (1 << v)
    
    # Precompute the "closure" for each subset:
    # A subset S is valid if for every i in S, all prerequisites of i are also in S.
    # We can check validity by expanding requirements.
    # 
    # For efficiency with N<=15, we iterate over all 2^N subsets.
    # For each subset, check if it's closed under prerequisites.
    # Also compute the profit.
    
    # Precompute value for each element
    val = [P[i] - C[i] for i in range(N)]
    
    # For each subset S (bitmask), check validity and compute sum
    # A subset S is valid iff for all i in S: (req[i] & S) == req[i]
    # i.e., req[i] is a subset of S
    
    # Precompute sum of values using subset sum DP (optional optimization)
    # But with N=15, 2^15 = 32768, straightforward is fine.
    
    # Precompute subset sums
    subset_val = [0] * (1 << N)
    for mask in range(1, 1 << N):
        # Find lowest set bit
        lsb = mask & (-mask)
        bit = lsb.bit_length() - 1
        subset_val[mask] = subset_val[mask ^ lsb] + val[bit]
    
    # Precompute combined requirement for each subset
    # For a subset S, combined_req[S] = union of req[i] for all i in S
    # S is valid iff combined_req[S] is a subset of S
    # We can compute combined_req incrementally
    combined_req = [0] * (1 << N)
    for mask in range(1, 1 << N):
        lsb = mask & (-mask)
        bit = lsb.bit_length() - 1
        combined_req[mask] = combined_req[mask ^ lsb] | req[bit]
    
    ans = 0  # empty set gives 0
    
    for mask in range(1, 1 << N):
        # Check if all requirements are satisfied: combined_req[mask] subset of mask
        if (combined_req[mask] & mask) == combined_req[mask]:
            if subset_val[mask] > ans:
                ans = subset_val[mask]
    
    print(ans)

main()

---

この解説は claude4.6opus-thinking によって生成されました。