概要

予算制限とプロジェクト間の競合関係がある中で、得られる利益を最大化するプロジェクトの組み合わせを選ぶ問題です。

考察

この問題は「どのプロジェクトを選ぶか」という組み合わせ最適化の問題です。素朴な方法として、すべてのプロジェクトの部分集合（組み合わせ）を試す方法があります。しかし、プロジェクト数 \(N\) が最大 \(18\) なので、部分集合の数は \(2^{18} = 262144\) 通りあり、これは十分に小さいため全探索が可能です。

それぞれの部分集合について、

1. 予算 \(K\) を超えていないか？
2. 競合するプロジェクトのペアが含まれていないか？

をチェックし、条件を満たすものの中で利益の合計が最大のものを求めればよいです。

競合関係は \(M\) 個のペアで与えられるので、選ばれたプロジェクトのリストから2つを選んで競合リストに含まれているかを確認します。Python の itertools.combinations を使うと便利です。

また、競合の判定を効率よく行うために、事前に競合情報を (u, v)（ただし \(u < v\)）という形で set に入れておくことで、存在判定を高速に行えます。

アルゴリズム

1. 全てのプロジェクトの部分集合をビット全探索で生成する（\(2^N\) 通り）。
2. 各部分集合について以下を確認：
   • 合計コストが予算 \(K\) 以内か？
   • 選ばれたプロジェクトの中に競合するペアが含まれていないか？
3. 条件を満たす中で利益が最大となるものを記録する。

計算量

• 時間計算量: \(O(2^N \cdot N^2)\)
  • 部分集合の個数：\(O(2^N)\)
  • 各部分集合に対して選ばれたプロジェクト数は最大 \(N\) 個、その中から2つ選ぶ組み合わせは最大 \(O(N^2)\)
• 空間計算量: \(O(M + N)\)
  • 競合情報を保存する set に \(O(M)\)、コスト・利益配列に \(O(N)\)

実装のポイント

• プロジェクトのインデックスは 1-based で入力されるが、内部処理では 0-based に変換して扱う。
• 競合情報を (u, v)（\(u < v\)）の形で統一することで、順序違いでも一致判定できるようにする。
• itertools.combinations を使うことで、選ばれたプロジェクトのペアを簡単に生成できる。

## ソースコード

```python
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
    K = int(data[idx]); idx += 1
    
    C = [0] * N
    P = [0] * N
    for i in range(N):
        C[i] = int(data[idx]); idx += 1
        P[i] = int(data[idx]); idx += 1
        
    conflicts = set()
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        u -= 1
        v -= 1
        if u > v:
            u, v = v, u
        conflicts.add((u, v))
        
    max_profit = 0
    
    # 全ての部分集合を試す (bit全探索)
    for mask in range(1 << N):
        cost = 0
        profit = 0
        selected = []
        for i in range(N):
            if mask & (1 << i):
                cost += C[i]
                profit += P[i]
                selected.append(i)
        if cost > K:
            continue
            
        # 選んだプロジェクト間に競合がないかチェック
        valid = True
        for u, v in combinations(selected, 2):
            if u > v:
                u, v = v, u
            if (u, v) in conflicts:
                valid = False
                break
        if valid:
            if profit > max_profit:
                max_profit = profit
                
    print(max_profit)

if __name__ == "__main__":
    main()

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