概要

経験者をちょうど \(M\) 人含むように \(K\) 人を選び、選んだ人のスキル合計 \(P\) を最大化する問題です。経験者・初心者を分けて「高いスキルから必要人数分取る」のが最適です。

考察

重要な気づき

条件は「選ばれた \(K\) 人のうち経験者がちょうど \(M\) 人」という 人数制約だけ です。経験者同士・初心者同士の間に相性や追加条件はありません。

このとき、最適解は直感的に次の通りです：

• 経験者枠 \(M\) 人は、経験者の中からスキルが高い順に \(M\) 人選ぶのが最善
• 初心者枠 \(K-M\) 人も、初心者の中からスキルが高い順に \(K-M\) 人選ぶのが最善

なぜなら、例えば経験者枠でスキルが低い人を選んでいるなら、その人をよりスキルの高い別の経験者に入れ替えても「経験者人数は変わらず」合計スキルだけが増えるため、低い人を選ぶ理由がありません（交換して改善できる）。

素朴なアプローチがダメな理由

\(N\) 人から \(K\) 人を選ぶ組合せは \(\binom{N}{K}\) 通りあり、\(N \le 2\times10^5\) では全探索は到底不可能です（TLE）。

この問題では人数制約だけなので、全探索せず「上位から取る」だけで最大化できます。

具体例

経験者のスキルが [10, 7, 3]、初心者が [8, 6, 1]、\(K=4, M=2\) のとき
- 経験者から上位2人：\(10 + 7\) - 初心者から上位2人：\(8 + 6\)
合計は \(31\) が最大になります。

アルゴリズム

1. 入力を読み、\(H_i\) に応じてスキル \(P_i\) を
   • 経験者リスト exp
   • 初心者リスト nov に分ける
2. そもそも条件を満たせるかチェックする
   
   • 経験者が \(M\) 人未満、または初心者が \(K-M\) 人未満なら不可能なので -1
3. exp と nov をそれぞれ降順ソートする
4. exp の先頭 \(M\) 個と nov の先頭 \(K-M\) 個を足し合わせて出力する

計算量

• 時間計算量: \(O(N \log N)\)（経験者・初心者それぞれのソートが支配的）
• 空間計算量: \(O(N)\)（スキルをリストに保持）

実装のポイント

• まず「条件を満たす選び方が存在するか」を必ず判定する（len(exp) < M や len(nov) < K-M）。

• 最大化したいので降順ソート（sort(reverse=True)）して先頭から必要個数を取る。

• Python では sum(exp[:M]) のようにスライスで簡潔に合計できる。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K, M = map(int, input().split())
    exp = []
    nov = []
    for _ in range(N):
        h, p = map(int, input().split())
        if h == 1:
            exp.append(p)
        else:
            nov.append(p)

    if len(exp) < M or len(nov) < K - M:
        print(-1)
        return

    exp.sort(reverse=True)
    nov.sort(reverse=True)
    ans = sum(exp[:M]) + sum(nov[:K - M])
    print(ans)

if __name__ == "__main__":
    main()

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