概要

\(N\) 人のメンバーから \(K\) 人を選び、その中に経験者がちょうど \(M\) 人含まれるようにして、スキルの合計を最大化する問題です。

考察

重要な気づき

この問題のポイントは、「経験者がちょうど \(M\) 人」という制約です。

• 選ぶ \(K\) 人の内訳は必ず「経験者 \(M\) 人 + 初心者 \((K-M)\) 人」になります
• 経験者と初心者を混ぜて比較する必要はなく、それぞれ独立に選べます

なぜ独立に選べるのか？

例えば \(K = 3\), \(M = 1\) の場合を考えます。 - 必ず経験者を1人、初心者を2人選ぶ必要があります - 経験者の枠は経験者同士で競合し、初心者の枠は初心者同士で競合します - よって、経験者の中でスキル上位 \(M\) 人、初心者の中でスキル上位 \((K-M)\) 人を選べばよいのです

具体例

N=5, K=3, M=1
経験者: スキル 100, 50
初心者: スキル 80, 70, 30

経験者1人を選ぶ → スキル上位1人 = 100 初心者2人を選ぶ → スキル上位2人 = 80, 70

答え: \(100 + 80 + 70 = 250\)

条件を満たせない場合

以下の場合は選び方が存在しません： - 経験者の人数が \(M\) 人未満 - 初心者の人数が \((K-M)\) 人未満

アルゴリズム

1. 分類: 全メンバーを経験者（\(H=1\)）と初心者（\(H=0\)）に分ける
2. 判定: 経験者が \(M\) 人以上、初心者が \((K-M)\) 人以上いるか確認。不足なら \(-1\) を出力
3. ソート: 経験者のスキルを降順ソート、初心者のスキルも降順ソート
4. 選択: 経験者から上位 \(M\) 人、初心者から上位 \((K-M)\) 人を選ぶ
5. 計算: 選んだメンバーのスキルの合計を出力

計算量

• 時間計算量: \(O(N \log N)\)

  • メンバーを分類するのに \(O(N)\)
  • ソートに \(O(N \log N)\)（経験者と初心者それぞれ、合計で \(N\) 人）
  • 上位の選択と合計計算に \(O(K)\)

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

  • 経験者リストと初心者リストを格納するため

実装のポイント

1. \(K - M = 0\) や \(M = 0\) の場合に注意: 初心者が0人必要な場合や経験者が0人必要な場合も正しく処理できるよう、空リストのスライスや sum([]) が正しく動作することを確認しましょう。

2. 降順ソートの使い方: sort(reverse=True) を使うと大きい順にソートされます。上位 \(X\) 人は先頭 \(X\) 要素をスライス [:X] で取得できます。

3. スキル値が大きい: \(P_i\) は最大 \(10^9\) で、\(K\) 人分の合計は最大 \(2 \times 10^{14}\) 程度になります。Python では整数オーバーフローを気にする必要はありませんが、C++ などでは long long を使う必要があります。

   ソースコード

def solve():
    N, K, M = map(int, input().split())
    
    experienced = []  # 経験者 (H=1)
    beginners = []    # 初心者 (H=0)
    
    for _ in range(N):
        H, P = map(int, input().split())
        if H == 1:
            experienced.append(P)
        else:
            beginners.append(P)
    
    # 経験者がちょうどM人、初心者がちょうどK-M人必要
    num_experienced_needed = M
    num_beginners_needed = K - M
    
    # 条件を満たせるか確認
    if len(experienced) < num_experienced_needed or len(beginners) < num_beginners_needed:
        print(-1)
        return
    
    # 経験者からスキル上位M人を選ぶ
    experienced.sort(reverse=True)
    selected_experienced = experienced[:num_experienced_needed]
    
    # 初心者からスキル上位(K-M)人を選ぶ
    beginners.sort(reverse=True)
    selected_beginners = beginners[:num_beginners_needed]
    
    # 合計を計算
    total = sum(selected_experienced) + sum(selected_beginners)
    
    print(total)

solve()

---

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