概要

\(N\) 人の社員から \(K\) 人を選んでチームを作り、能力値の合計から相性の悪いペアによる減少分を引いた「チームの総合力」を最大化する問題です。

考察

重要な気づき

• \(N \leq 18\) という制約が非常に小さいことに注目します
• \(N\) 人から \(K\) 人を選ぶ組み合わせの総数は \(\binom{N}{K}\) 通りです
• \(N = 18\) のとき、最大で \(\binom{18}{9} = 48620\) 通り程度しかありません

素朴なアプローチで十分な理由

通常、組み合わせを全列挙するアプローチは指数的な計算量になり、\(N\) が大きいとTLEになります。しかし、この問題では： - \(N \leq 18\) と小さい - 組み合わせの数は最大でも約5万通り - 各組み合わせに対する処理も \(O(K + M)\) 程度

したがって、全探索で十分間に合います。

具体例

例えば \(N = 4\)、\(K = 2\)、社員の能力値が \([10, 20, 30, 5]\)、相性の悪いペアが \((1, 3)\) で減少量 \(15\) の場合：

アルゴリズム

1. 全組み合わせの列挙: itertools.combinations を使って、\(N\) 人から \(K\) 人を選ぶすべての組み合わせを生成
2. 各組み合わせについて:
   • 選んだ社員の能力値を合計する
   • 相性の悪いペア \((U_j, V_j)\) について、両方ともチームに含まれていれば \(B_j\) を減算
3. 最大値の更新: 計算した総合力が現在の最大値より大きければ更新
4. 結果の出力: 最終的な最大値を出力

計算量

• 時間計算量: \(O(\binom{N}{K} \times (K + M))\)

  • \(\binom{N}{K}\) 通りの組み合わせを列挙
  • 各組み合わせで能力値の合計に \(O(K)\)、ペアの判定に \(O(M)\)
  • \(N = 18\) のとき、最大で約 \(48620 \times (18 + 153) \approx 8.3 \times 10^6\) 回程度の演算

• 空間計算量: \(O(N + M)\)

  • 能力値の配列 \(A\) に \(O(N)\)
  • 相性の悪いペアのリストに \(O(M)\)
  • チームをsetで管理するのに \(O(K)\)

実装のポイント

1. 0-indexed への変換: 入力の社員番号は1から始まるため、配列アクセスのために -1 して0-indexedに変換する

2. set の活用: 選んだメンバーを set に格納することで、特定の社員がチームに含まれているかの判定を \(O(1)\) で行える

3. 初期値の設定: 最大値の初期値は -float('inf') にしておくと、減少分が大きくて負になるケースでも正しく処理できる

   ソースコード

from itertools import combinations

def solve():
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # 相性の悪いペアの情報を格納
    bad_pairs = []
    for _ in range(M):
        U, V, B = map(int, input().split())
        bad_pairs.append((U - 1, V - 1, B))  # 0-indexed に変換
    
    max_power = -float('inf')
    
    # N人からK人を選ぶすべての組み合わせを列挙
    for team in combinations(range(N), K):
        team_set = set(team)
        
        # 選んだ社員の能力値の合計
        total = sum(A[i] for i in team)
        
        # 相性の悪いペアによる減少分を計算
        for U, V, B in bad_pairs:
            if U in team_set and V in team_set:
                total -= B
        
        max_power = max(max_power, total)
    
    print(max_power)

solve()

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