概要

\(N\) 人のメンバーから、「経験者がちょうど \(M\) 人」「合計でちょうど \(K\) 人」という条件を満たすようにメンバーを選び、そのスキルの合計値を最大化する問題です。

考察

この問題のポイントは、「経験者から選ぶ人数」と「初心者から選ぶ人数」が固定されている点にあります。

• 選ぶ人数の合計：\(K\) 人
• 選ぶ経験者の人数：\(M\) 人
• 選ぶ初心者の人数：\(K - M\) 人

「合計のスキルを最大化したい」という目的を達成するためには、経験者のグループからスキルの高い順に \(M\) 人、初心者のグループからスキルの高い順に \(K - M\) 人を選べばよいことがわかります。経験者と初心者の選択は互いに影響しない（独立している）ため、それぞれのグループで上位から選ぶという単純な「貪欲法」の考え方が適用できます。

また、以下のいずれかの条件に当てはまる場合は、指定された人数を確保できないため、答えは \(-1\) となります。 - 全体の経験者の人数が \(M\) 人未満である。 - 全体の初心者の人数が \(K - M\) 人未満である。

アルゴリズム

1. グループ分け: 全メンバーを経験者（\(H_i=1\)）と初心者（\(H_i=0\)）の 2 つのリストに振り分けます。
2. 条件チェック: 経験者のリストの要素数が \(M\) 以上、かつ初心者のリストの要素数が \(K - M\) 以上であることを確認します。満たさない場合は \(-1\) を出力して終了します。
3. ソート: それぞれのリストをスキルの高い順（降順）にソートします。
4. 合計計算: 経験者リストの先頭 \(M\) 個の和と、初心者リストの先頭 \(K - M\) 個の和を計算し、その合計を出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • メンバーの振り分けに \(O(N)\)、リストのソートに \(O(N \log N)\) かかります。
• 空間計算量: \(O(N)\)
  • メンバーのスキルを保存するためのリストに \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) が最大 \(2 \times 10^5\) と比較的大きいため、Python の場合は sys.stdin.read().split() などを用いて一括で入力を取得すると実行時間を短縮できます。

• スライスの活用: Python では sum(list[:count]) のようにスライスを使うことで、上位数件の合計を簡潔に記述できます。

• コーナーケース: \(M=0\) や \(M=K\) の場合も、このアルゴリズムで正しく処理可能です。

  ソースコード

import sys

def main():
    # 入力を標準入力からすべて読み込み、空白で分割してトークンのリストを作成します
    # これは大量の入力を高速に処理するための一般的な手法です
    try:
        data = sys.stdin.read().split()
    except EOFError:
        return
        
    if not data:
        return
    
    # N: メンバーの総数, K: 選ぶメンバーの人数, M: 必要な経験者の人数
    N = int(data[0])
    K = int(data[1])
    M = int(data[2])
    
    # 経験者のスキルと初心者のスキルをそれぞれ別のリストに格納します
    experienced_skills = []
    beginner_skills = []
    
    # data[3]以降に各メンバーのH_iとP_iが交互に並んでいます
    # 各メンバーの情報をループで処理します
    ptr = 3
    for _ in range(N):
        # h: 経験の有無 (1なら経験者, 0なら初心者), p: スキル
        h = data[ptr]
        p = int(data[ptr+1])
        if h == '1':
            experienced_skills.append(p)
        else:
            beginner_skills.append(p)
        ptr += 2
        
    # 選ぶK人のうち経験者がちょうどM人必要なので、初心者はちょうどK-M人必要です
    num_beginners_needed = K - M
    
    # 必要な人数分それぞれのメンバーが存在するか確認します
    # 存在しない場合は条件を満たす選び方ができないため -1 を出力します
    if len(experienced_skills) < M or len(beginner_skills) < num_beginners_needed:
        print("-1")
        return
        
    # 総合力（スキルの合計）を最大化するため、それぞれのリストを降順（大きい順）にソートします
    experienced_skills.sort(reverse=True)
    beginner_skills.sort(reverse=True)
    
    # 経験者の上位M人のスキル合計と、初心者の上位K-M人のスキル合計を計算します
    # Pythonのスライスとsum関数を用いて効率的に合計を求めます
    max_total_skill = sum(experienced_skills[:M]) + sum(beginner_skills[:num_beginners_needed])
    
    # 結果を出力します
    print(max_total_skill)

if __name__ == '__main__':
    main()

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