概要

青木君を必ずチームに含め、残りのメンバーは他の選手から実力値が高い順に選ぶ問題です。

考察

問題の理解

この問題では、\(N\) 人の候補選手から \(K\) 人のチームを作ります。ただし、以下の制約があります： - 選手 \(T\)（青木君）は必ずメンバーに入れる - 残り \(K-1\) 人は、青木君以外から実力値の高い順に選ぶ

重要な気づき

1. 青木君は無条件でチームに入るので、青木君の実力値 \(A_T\) は必ず合計に含まれます
2. 残りの選手は青木君を除いた \(N-1\) 人です
3. その \(N-1\) 人から実力値が高い上位 \(K-1\) 人を選べばよいです

具体例で考える

例えば、\(N=5\), \(K=3\), \(T=2\) で、実力値が \(A = [10, 5, 30, 20, 15]\) の場合： - 青木君（選手2）の実力値は \(5\) - 青木君以外の選手の実力値は \([10, 30, 20, 15]\) - これを降順ソートすると \([30, 20, 15, 10]\) - 上位 \(K-1=2\) 人を選ぶと、実力値 \(30\) と \(20\) の選手 - 合計は \(5 + 30 + 20 = 55\)

素朴なアプローチで問題ないか？

この問題では、ソートを使うアプローチで十分高速です。\(N \leq 2 \times 10^5\) に対して \(O(N \log N)\) のソートは余裕で間に合います。

アルゴリズム

1. 青木君の実力値 \(A_{T-1}\)（0-indexed）を取得する
2. 青木君以外の全選手の実力値をリストに集める
3. そのリストを実力値の降順（高い順）にソートする
4. ソートしたリストの先頭から \(K-1\) 人分の実力値を取り出す
5. 青木君の実力値と、取り出した \(K-1\) 人分の実力値を合計して出力する

青木君の実力値 + (青木君以外で上位 K-1 人の実力値の和)

計算量

• 時間計算量: \(O(N \log N)\)
  • 青木君以外の選手をリストに集める: \(O(N)\)
  • ソート: \(O(N \log N)\)
  • 上位 \(K-1\) 人の合計を計算: \(O(K)\)
  • 全体として \(O(N \log N)\) が支配的
• 空間計算量: \(O(N)\)
  • 青木君以外の選手の実力値を格納するリストに \(O(N)\)

実装のポイント

1. インデックスの変換: 問題文では選手番号は1から始まる（1-indexed）が、Pythonのリストは0から始まる（0-indexed）ため、青木君のインデックスは T-1 となります。

2. 青木君を除外する処理: ループで全選手を見て、インデックスが T-1 でない選手だけを別リストに追加します。

3. 降順ソート: sort(reverse=True) を使うことで、実力値の高い順に並べ替えます。

4. 合計の計算: スライスを使って sum(others[:K-1]) としても良いですが、コードではループで明示的に足しています。どちらでも正しく動作します。

   ソースコード

def solve():
    N, K, T = map(int, input().split())
    A = list(map(int, input().split()))
    
    # 青木君の実力値（0-indexedなのでT-1）
    aoki_power = A[T - 1]
    
    # 青木君以外の選手の実力値リスト
    others = []
    for i in range(N):
        if i != T - 1:
            others.append(A[i])
    
    # 実力値の高い順にソート
    others.sort(reverse=True)
    
    # 青木君 + 残りK-1人の実力値の合計
    total = aoki_power
    for i in range(K - 1):
        total += others[i]
    
    print(total)

solve()

---

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