概要

\(N\) 人の候補選手から \(K\) 人のチームを作る際、特定の選手（青木君）を必ず含めた上で、残りの \(K-1\) 人を実力値が高い順に選んだときの、チーム合計実力値を求める問題です。

考察

この問題のポイントは、「青木君を固定し、残りの枠を最適に埋める」という考え方です。

1. 青木君の扱い: 選手番号 \(T\) の青木君は、実力値に関わらず必ずチームに入ります。そのため、まず青木君の実力値 \(A_T\) を確保しておきます。
2. 残りのメンバー選定: チームの定員は \(K\) 人なので、青木君以外の選手から残り \(K-1\) 人を選ぶ必要があります。合計値を最大化するためには、青木君を除いた \(N-1\) 人の候補の中から、実力値が大きい順に \(K-1\) 人を選べばよいことになります。
3. 効率的な選択: 「大きい順に選ぶ」ためには、データを大きい順（降順）に並び替える（ソートする）のが最も効率的です。

例えば、選手の実力値が \([10, 30, 20, 40]\) で \(K=3\)、青木君が選手 1 (\(A_1=10\)) の場合： - 青木君 (10) を選ぶ。 - 残りは \([30, 20, 40]\)。 - これを降順に並べると \([40, 30, 20]\)。 - 上位 \(K-1 = 2\) 人（40 と 30）を選ぶ。 - 合計は \(10 + 40 + 30 = 80\) となります。

アルゴリズム

1. 入力から \(N, K, T\) および各選手の実力値リスト \(A\) を受け取ります。
2. 青木君の実力値 \(A_T\) を変数に保存します（プログラミング言語の配列は 0 番目から始まることが多いため、インデックスの扱いに注意します）。
3. リスト \(A\) から青木君の実力値を除去します。
4. 残った \(N-1\) 人の実力値リストを、大きい順（降順）にソートします。
5. ソート後のリストの先頭から \(K-1\) 個の要素の和を求め、それに青木君の実力値を加算したものが答えとなります。

計算量

• 時間計算量: \(O(N \log N)\)
  • データの読み込みに \(O(N)\)、リストのソートに \(O(N \log N)\)、上位 \(K-1\) 人の合計計算に \(O(K)\) かかります。全体ではソートの計算量が支配的になります。\(N = 2 \times 10^5\) であるため、この計算量で十分に制限時間内に間に合います。
• 空間計算量: \(O(N)\)
  • 全選手の実力値をリストに格納するため、選手数 \(N\) に比例したメモリを使用します。

実装のポイント

• 1-indexed への対応: 問題文では選手番号が \(1\) から \(N\) で与えられますが、Python のリストは \(0\) から始まるため、青木君のインデックスは T-1 となります。

• K=1 の場合: \(K=1\) のときは青木君一人だけのチームになります。この場合、ソート後のリストから選ぶ人数は \(K-1 = 0\) 人となり、合計には青木君の実力値のみが反映されるように実装します（Python のスライス a[:0] は空のリストを返すため、正しく動作します）。

• 高速な入出力: \(N\) が最大 \(2 \times 10^5\) と大きいため、sys.stdin.read().split() を用いるなどして入力を高速に処理するのが望ましいです。

  ソースコード

import sys

def solve():
    # 入力をすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    k = int(input_data[1])
    t = int(input_data[2])
    
    # 選手の実力値をリストに格納
    a = list(map(int, input_data[3:]))
    
    # 青木君の実力値を取得（選手番号 T は 1-indexed）
    aoki_ability = a[t-1]
    
    # 青木君を候補から除外する
    a.pop(t-1)
    
    # 残りの候補を実力値の高い順（降順）にソート
    a.sort(reverse=True)
    
    # 青木君の実力値と、残りから選ぶ K-1 人の実力値の合計を計算
    # K=1 の場合は sum(a[:0]) となり 0 が加算される
    ans = aoki_ability + sum(a[:k-1])
    
    # 結果を出力
    print(ans)

if __name__ == '__main__':
    solve()

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