概要

\(N\) 個の研究テーマから前提関係（\(U_j\) を選ぶなら \(V_j\) も選ぶ）を満たすように部分集合を選び、得られる利益（価値 \(P_i\) から費用 \(C_i\) を引いた値）の合計を最大化する問題です。\(N \le 15\) と小さい制約に着目し、bit全探索を用いて解くことができます。

考察

この問題は、一般に「最大重み閉包問題（燃やす埋める問題）」として知られており、最大流（最小カット）アルゴリズムを用いて解くことも可能な形をしています。しかし、本問題では制約として \(N \le 15\) と非常に小さな値が設定されています。

研究テーマの「選ぶ・選ばない」の組み合わせは全部で \(2^N\) 通りであり、\(N=15\) のとき最大でも \(2^{15} = 32,768\) 通りしかありません。したがって、高度なアルゴリズムを使わなくても、すべての選び方を全探索することで十分に制限時間内に解くことができます。

素朴に配列やリストを用いて集合を管理・判定すると定数倍の実行時間がかさむ可能性がありますが、集合を整数のビット列に見立てる「bit演算」を活用することで、前提関係の判定や利益の計算を非常に高速に行うことができます。

アルゴリズム

1. 利益の計算: 各テーマ \(i\) を選んだときの純利益を \(W_i = P_i - C_i\) としてあらかじめ計算しておきます。

2. 前提条件のbit表現: テーマ \(i\) を選んだときに必須となるテーマの集合を、整数（bitマスク） req[i] として管理します。例えば、テーマ \(0\) がテーマ \(1\) と \(2\) を前提とするなら、req[0] の \(1\) ビット目と \(2\) ビット目を立てます（二進数で ...0110）。

3. 部分集合の利益の事前計算: \(0\) から \(2^N - 1\) までのすべての選び方（mask）について、選んだテーマの利益の合計を計算し、配列 profit_sum に保存します。

4. 条件判定と最大値の更新: すべての mask について、前提関係を満たしているかを調べます。

   • mask に含まれるすべてのテーマ \(i\) について、mask & req[i] == req[i] が成り立てば、前提となるテーマがすべて mask に含まれていることになります。
   • 条件を満たす mask の中で、利益の合計の最大値を求めます。何も選ばない場合（mask = 0）の利益は \(0\) なので、最大値の初期値は \(0\) としておきます。

計算量

• 時間計算量: \(O(N 2^N)\) 部分集合の総数が \(2^N\) 通りあり、それぞれの集合について前提条件を満たすかのチェックに \(O(N)\) の時間がかかります。\(N=15\) のとき \(15 \times 32,768 \approx 5 \times 10^5\) 回程度の演算となり、実行時間制限（通常2秒）に余裕で間に合います。
• 空間計算量: \(O(2^N)\) 各部分集合の利益の合計を保存するための配列 profit_sum に \(2^N\) 個の要素を保持するためです。\(N=15\) なら要素数は \(32,768\) となり、メモリ制限に対しても全く問題ありません。

実装のポイント

• bit演算による集合操作: あるテーマ \(i\) が mask に含まれているかは mask & (1 << i) で判定できます。また、必須テーマがすべて含まれているかの判定 (mask & req[i]) == req[i] は、bit演算ならではの簡潔で高速な記述です。

• LSB（最下位ビット）を使った高速な事前計算: profit_sum を求める際、lsb = mask & -mask によって mask の中で一番右にある 1 のビットだけを取り出すことができます。これを利用して profit_sum[mask] = profit_sum[mask ^ lsb] + profits[i] と漸化式のように計算することで、各 mask の利益計算を \(O(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])
    
    profits = []
    idx = 2
    for _ in range(N):
        P = int(input_data[idx])
        C = int(input_data[idx+1])
        profits.append(P - C)
        idx += 2
        
    req = [0] * N
    for _ in range(M):
        u = int(input_data[idx]) - 1
        v = int(input_data[idx+1]) - 1
        req[u] |= (1 << v)
        idx += 2
        
    profit_sum = [0] * (1 << N)
    for mask in range(1, 1 << N):
        lsb = mask & -mask
        i = lsb.bit_length() - 1
        profit_sum[mask] = profit_sum[mask ^ lsb] + profits[i]
        
    max_profit = 0
    for mask in range(1 << N):
        valid = True
        for i in range(N):
            if (mask & (1 << i)) and ((mask & req[i]) != req[i]):
                valid = False
                break
        if valid:
            if profit_sum[mask] > max_profit:
                max_profit = profit_sum[mask]
                
    print(max_profit)

if __name__ == '__main__':
    solve()

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