概要

\(N\) 個のプロジェクトから、競合関係を避けつつ予算内で利益を最大化する組み合わせを選ぶ問題です。\(N \leq 18\) という制約から、ビット全探索で全ての部分集合を調べます。

考察

重要な気づき

• \(N \leq 18\) という制約が非常に重要です
• 全ての選び方は \(2^N = 2^{18} = 262144\) 通りしかありません
• これは十分小さいので、全探索が可能です

なぜビット全探索か

各プロジェクトについて「選ぶ / 選ばない」の2択があるので、選択状態は \(N\) ビットの整数で表現できます。

例えば \(N = 4\) の場合： - 0101 (= 5) → プロジェクト1と3を選択 - 1110 (= 14) → プロジェクト2, 3, 4を選択

競合関係のチェック方法

競合関係もビットマスクで管理すると効率的です。

例：プロジェクト0と2が競合、プロジェクト0と3が競合の場合 - conflict[0] = 1100 (= 12) → 0と競合するのは2と3

選択したプロジェクト \(i\) について、mask & conflict[i] が 0 でなければ、\(i\) と競合するプロジェクトも同時に選ばれているので不正です。

アルゴリズム

1. 入力の読み込み: 各プロジェクトのコスト・利益と、競合関係を読み込む

2. 競合関係のビットマスク化: 各プロジェクト \(i\) について、競合するプロジェクトの集合を conflict[i] にビットマスクとして格納

3. 全部分集合の列挙: \(0\) から \(2^N - 1\) までの各整数 mask について：

   • mask のビットが立っている位置が選択するプロジェクト
   • 選択したプロジェクト間に競合がないかチェック
   • 総コストが予算 \(K\) 以内かチェック
   • 両方満たせば、総利益を計算して最大値を更新

4. 結果の出力: 最大利益を出力

mask = 0110 (プロジェクト1, 2を選択)
↓
プロジェクト1について: mask & conflict[1] をチェック
プロジェクト2について: mask & conflict[2] をチェック
↓
競合なし & 予算内 → 利益を計算

計算量

• 時間計算量: \(O(2^N \cdot N)\)
  • \(2^N\) 個の部分集合それぞれに対して、\(N\) 個のプロジェクトを確認
  • \(N = 18\) の場合、約 \(262144 \times 18 \approx 4.7 \times 10^6\) 回の操作
• 空間計算量: \(O(N)\)
  • 競合関係を格納する配列 conflict のサイズ

実装のポイント

1. 0-indexed への変換: 入力ではプロジェクト番号が 1 から始まるので、\(U, V\) を読み込んだ後に 1 を引いて 0-indexed にする

2. ビット演算の基本:

   • mask & (1 << i): mask の \(i\) ビット目が立っているか判定
   • conflict[U] |= (1 << V): conflict[U] の \(V\) ビット目を立てる

3. 早期打ち切り: 競合が見つかった時点で break してループを抜けることで、無駄な計算を省く

4. 初期値: 何も選ばない場合（mask = 0）も有効な選択なので、max_profit の初期値は 0 でOK

   ソースコード

def solve():
    N, M, K = map(int, input().split())
    
    projects = []
    for i in range(N):
        C, P = map(int, input().split())
        projects.append((C, P))
    
    # 競合関係をビットマスクで管理
    conflict = [0] * N
    for j in range(M):
        U, V = map(int, input().split())
        U -= 1  # 0-indexed
        V -= 1
        conflict[U] |= (1 << V)
        conflict[V] |= (1 << U)
    
    max_profit = 0
    
    # 全ての部分集合を列挙 (2^N通り)
    for mask in range(1 << N):
        # この部分集合が競合関係を満たすかチェック
        valid = True
        total_cost = 0
        total_profit = 0
        
        for i in range(N):
            if mask & (1 << i):
                # プロジェクトiが選ばれている
                # iと競合するプロジェクトが同時に選ばれていないかチェック
                if mask & conflict[i]:
                    valid = False
                    break
                total_cost += projects[i][0]
                total_profit += projects[i][1]
        
        if valid and total_cost <= K:
            max_profit = max(max_profit, total_profit)
    
    print(max_profit)

solve()

---

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