概要

この問題は、予算制限（ナップサック問題の要素）と、同時に選べないプロジェクトのペア（最大独立集合問題の要素）という2つの制約がある中で、得られる利益を最大化する問題です。プロジェクト数 \(N\) が最大 18 と非常に小さいことが解法の鍵となります。

考察

1. 制約に着目する

まず、プロジェクト数 \(N \leq 18\) という制約に注目します。一般に \(N\) が 20 以下の場合は、全探索やビットを用いた指数時間アルゴリズム（\(2^N\) など）が有効である可能性が高いです。

2. 単純なナップサック問題との違い

もし「競合関係」がなければ、これは典型的な「ナップサック問題」です。しかし、今回は「プロジェクト \(A\) と \(B\) は同時に選べない」という制約があるため、通常の動的計画法（DP）をそのまま適用するのは困難です。

3. 全探索の検討

すべてのプロジェクトの選び方は \(2^N\) 通りあります。\(N=18\) のとき、\(2^{18} = 262,144\) です。この程度の数であれば、すべての組み合わせを調べることが十分に可能です。各組み合わせについて、「競合がないか」と「予算内か」を判定し、条件を満たすもののうち利益が最大のものを探せばよいことになります。

4. 効率的な探索

単純にすべての組み合わせを生成してから判定する代わりに、1つずつプロジェクトを追加していく過程で「競合が発生しないものだけ」を残していくことで、効率的に探索できます。

アルゴリズム

ビットを用いた動的計画法、あるいは「有効な独立集合（競合のない集合）」を順次構築していく手法を採用します。

1. 競合関係の整理: 各プロジェクト \(i\) について、それより手前の番号のプロジェクトのうち、どれと競合するかをビットマスク adj[i] で管理します。
2. 有効な集合の保持: 「現在までにわかっている、競合のないプロジェクトの組み合わせ（独立集合）」をリストで保持します。各要素は (ビットマスク, 合計コスト, 合計利益) です。
3. プロジェクトの追加: プロジェクト \(i = 0, 1, \dots, N-1\) について順に以下の操作を行います。
   • 現在保持しているすべての「有効な集合」に対して、プロジェクト \(i\) を追加できるか試します。
   • 追加できる条件は以下の2点です：
     • 現在の集合に含まれるプロジェクトと、プロジェクト \(i\) が競合しない（mask & adj[i] == 0）。
     • プロジェクト \(i\) を加えた後の合計コストが \(K\) 以下である。
   • 条件を満たす場合、新しい「有効な集合」としてリストに追加します。
4. 最大値の更新: 新しく作成された集合の利益を確認し、これまでの最大利益を更新していきます。

計算量

• 時間計算量: \(O(2^N)\) 最悪の場合（競合が全くない場合）、有効な組み合わせの数は \(2^N\) 個になります。\(N=18\) では約 \(2.6 \times 10^5\) であり、各ステップの処理は高速なため制限時間内に十分収まります。
• 空間計算量: \(O(2^N)\) 有効な組み合わせの情報をリストに保持するため、最大で \(2^N\) 個の要素を格納するメモリが必要です。

実装のポイント

• ビット演算の活用: プロジェクトの集合を整数（ビットマスク）で表すことで、競合判定を m & adj[i] という非常に高速なビット演算で行うことができます。

• 逐次的な更新: コードでは masks, costs_list, profits_list というリストを使い、新しいプロジェクトを検討するたびに既存のリストに新しい状態を追加していく形式をとっています。これにより、無駄な状態を探索せずに済みます。

  ソースコード

import sys

def solve():
    # Read all input at once and split into a list of strings
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Use an iterator to process the input data efficiently
    it = iter(input_data)
    N = int(next(it))
    M = int(next(it))
    K = int(next(it))
    
    costs = []
    profits = []
    for _ in range(N):
        costs.append(int(next(it)))
        profits.append(int(next(it)))
        
    # adj[i] is a bitmask of projects with indices less than i that conflict with project i
    adj = [0] * N
    for _ in range(M):
        u = int(next(it)) - 1
        v = int(next(it)) - 1
        # We only care about conflicts with previously processed projects (index < current i)
        if u < v:
            adj[v] |= (1 << u)
        else:
            adj[u] |= (1 << v)
        
    # We maintain lists of all valid independent sets found so far.
    # Each set is represented by its bitmask, total cost, and total profit.
    masks = [0]
    costs_list = [0]
    profits_list = [0]
    max_profit = 0
    
    # Iterate through each project to decide whether to include it
    for i in range(N):
        c = costs[i]
        p = profits[i]
        a = adj[i]
        
        new_masks = []
        new_costs = []
        new_profits = []
        
        # Try adding project i to all currently known valid independent sets
        for m, c_total, p_total in zip(masks, costs_list, profits_list):
            # Check for conflicts with projects already in the set m
            # and verify if the total cost is within the budget K
            if not (m & a):
                nc = c_total + c
                if nc <= K:
                    np = p_total + p
                    new_masks.append(m | (1 << i))
                    new_costs.append(nc)
                    new_profits.append(np)
                    if np > max_profit:
                        max_profit = np
        
        # Add the newly formed independent sets to our collection
        masks.extend(new_masks)
        costs_list.extend(new_costs)
        profits_list.extend(new_profits)
        
    # Output the maximum profit found
    print(max_profit)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。