概要

\(N \le 15\) と小さいので、研究テーマの選び方（部分集合）を全探索し、前提関係を満たす集合の中で \(\sum_{i\in S}(P_i-C_i)\) を最大化します。

考察

この問題の制約は「\(U\) を選ぶなら \(V\) も必ず選ぶ」という 含意（依存関係） です。
つまり、選んだ集合 \(S\) は次を満たす必要があります：

• すべての前提 \((U,V)\) について、\(U \in S \Rightarrow V \in S\)

循環（例：\(A \Rightarrow B\), \(B \Rightarrow A\)）があっても、「\(A\) を選ぶなら \(B\) も必要」「\(B\) を選ぶなら \(A\) も必要」なので、結局 \(\{A\}\) だけは不可能で、\(\{A,B\}\) か空集合しか選べない、という形で自然に処理できます（特別な強連結成分分解などは不要）。

素朴なアプローチがなぜ通る/通らないか

• \(N\) が大きいと部分集合全探索は \(2^N\) で爆発しますが、この問題は \(N \le 15\) なので \(2^{15}=32768\) 程度で、十分間に合います。
• 逆に「依存関係を満たす集合を賢く生成する」ような方法を考える必要はありません。全ての集合を試し、条件を満たすか判定するだけで確実に正解できます。

重要な工夫：ビットマスクで高速判定

各テーマ \(u\) について「\(u\) を選ぶなら必要なテーマ集合」をビット集合 req[u] として持つと、

• ある集合 mask が与えられたとき、
• mask に \(u\) が含まれるなら、req[u] の要素もすべて mask に含まれていないといけない

をビット演算で高速に判定できます。

例えば req[u] & ~mask が 0 でなければ、「必要なもののうち選ばれていないものが存在する」ので条件違反です。

アルゴリズム

1. 各テーマ \(i\) の価値を \(w_i = P_i - C_i\) として計算しておく。
2. 前提関係 \((U,V)\) ごとに、req[U] に \(V\) をビットで追加する（req[U] |= 1<<V）。
3. 全ての部分集合 mask（\(0\) から \(2^N-1\)）を試す。
   • 各 \(u\) について、mask に \(u\) が含まれるなら、req[u] が mask に含まれているかをチェックする。
     • 具体的には req[u] & ~mask != 0 なら不正。
   • 条件を満たすなら、その集合の得点 \(\sum w_i\) を計算して最大値を更新する。
4. 最大値を出力する（空集合は得点 \(0\)）。

簡単な例

\(N=3\)、前提が「1 を選ぶなら 2」だとします。
集合 \(S=\{1\}\) は 2 がないので不正ですが、\(S=\{1,2\}\) は正です。
この「正しい集合かどうか」を、req[1] に 2 のビットを立てておけば一瞬で判定できます。

計算量

• 時間計算量: \(O(N\cdot 2^N)\)
  （各 mask について最大 \(N\) 個のチェック＋合計計算を行うため）
• 空間計算量: \(O(N)\)
  （w と req を持つだけ）

実装のポイント

• テーマ集合は mask（\(0 \le mask < 2^N\)）の ビットマスク で表すと実装が簡潔で高速です。

• 前提関係は req[u]（ビット集合）として保持し、判定は req[u] & ~mask を使うと速いです。

• 最大値は空集合（mask=0）のとき \(0\) なので、初期値 ans=0 でよいです（負の得点しか作れない場合は空集合が最適）。

  ソースコード

import sys

def main():
    it = list(map(int, sys.stdin.buffer.read().split()))
    if not it:
        return
    idx = 0
    N = it[idx]; idx += 1
    M = it[idx]; idx += 1

    w = [0] * N
    for i in range(N):
        P = it[idx]; C = it[idx + 1]; idx += 2
        w[i] = P - C

    req = [0] * N
    for _ in range(M):
        U = it[idx] - 1
        V = it[idx + 1] - 1
        idx += 2
        req[U] |= 1 << V

    ans = 0
    for mask in range(1 << N):
        ok = True
        for u in range(N):
            if (mask >> u) & 1:
                if req[u] & ~mask:
                    ok = False
                    break
        if not ok:
            continue
        s = 0
        for i in range(N):
            if (mask >> i) & 1:
                s += w[i]
        if s > ans:
            ans = s

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。