概要

研究テーマの集合を選び、得られる価値の合計から費用の合計を引いた値を最大化する問題です。ただし、いくつかの前提条件（依存関係）があり、これらをすべて満たす必要があります。

考察

この問題では、研究テーマの数 \(N\) が最大で \(15\) と小さいため、すべてのテーマの部分集合（\(2^N\)通り）を全探索することが可能です。それぞれの集合について、前提条件をすべて満たしているかどうかを確認し、満たしていればその集合の「価値−費用」の合計を計算します。

素朴な方法としては、全テーマの部分集合を生成し、それぞれに対して依存関係をチェックすればよいのですが、もし依存関係が循環していたり、複雑な構造だったとしても、単純に「\(u\) を選んでいるのに \(v\) を選んでいない」という違反がないかを確認すれば十分です。

このように、全探索を行うことで最適解を求めることができます。より大きい \(N\) であれば強連結成分分解などが必要になるかもしれませんが、今回の制約では不要です。

アルゴリズム

1. 各研究テーマの「価値−費用」を前計算しておきます。
2. ビット全探索により、\(0\) から \(2^N - 1\) までの各ビット列に対応するテーマの集合を生成します。
3. 各集合に対して、すべての依存関係 \((u, v)\) について、「\(u\) を選んでいるのに \(v\) を選んでいない」場合があれば不適切なのでスキップします。
4. 適切な集合であれば、その「価値−費用」の合計を計算し、これまでの最大値を更新します。
5. 最終的な最大値を出力します。

計算量

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

ここで、\(N\) は研究テーマの数、\(M\) は依存関係の数です。\(N \leq 15\) より、\(2^N \leq 32768\) であり、十分高速に動作します。

実装のポイント

• ビット演算を使って部分集合を生成する際、テーマのインデックスが 1-based なので注意が必要です（コードでは i+1 としている）。

• 依存関係のチェックは、選択されたテーマの集合を set に入れておくと、含まれているかどうかの判定が高速に行えます。

• 空集合に対応するケース（利益が 0）も考慮されていることに注意してください。

  ソースコード

from itertools import combinations

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    P = [0] * (N+1)
    C = [0] * (N+1)
    for i in range(1, N+1):
        P[i] = int(data[idx])
        idx += 1
        C[i] = int(data[idx])
        idx += 1
        
    # 依存関係をリストで保持
    deps = []
    for _ in range(M):
        u = int(data[idx])
        idx += 1
        v = int(data[idx])
        idx += 1
        deps.append((u, v))
    
    # 各テーマの価値 - 費用
    diff = [P[i] - C[i] for i in range(N+1)]
    
    max_profit = 0  # 空集合の場合は0
    
    # 全ての部分集合を試す (bit全探索)
    for mask in range(1 << N):
        valid = True
        selected = set()
        for i in range(N):
            if mask & (1 << i):
                selected.add(i+1)
        
        # 依存関係チェック
        for u, v in deps:
            if u in selected and v not in selected:
                valid = False
                break
                
        if not valid:
            continue
            
        profit = sum(diff[i] for i in selected)
        if profit > max_profit:
            max_profit = profit
            
    print(max_profit)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。