概要

\(N\) 人の参加者のうち合計スコアが \(K\) 以上の本戦進出者を特定し、指定された優先順位に従ってシード番号（\(1, 2, \dots\)）を割り当て、各参加者のシード番号（進出していない場合は \(-1\)）を元の番号順に出力する問題です。

考察

素朴なアプローチとその問題点

各進出者について「自分より優先順位が高い参加者が何人いるか」を全員と比較して数える方法が考えられます。しかし、この方法では1人あたり \(O(N)\) の時間がかかり、全体で \(O(N^2)\) の計算量となります。本問では \(N \le 10^5\) であるため、計算回数が約 \(10^{10}\) 回となり、実行時間制限（TLE）に間に合いません。

効率的なアプローチ

進出者を効率よく順位づけするために、ソート（並び替え） を利用します。

本戦に進出する条件は \(A_i + B_i \ge K\) です。この条件を満たす参加者のみを抽出したのち、以下の優先順位に従ってソートを行います。 1. 合計スコアが大きい順（降順） 2. 合計スコアが同じ場合、参加者番号が小さい順（昇順）

Pythonの標準のソート（昇順）を利用する場合、合計スコアの符号を反転させた値（\(- (A_i + B_i)\)）と参加者番号 \(i\) をペア (-score, i) にしてリストに持たせると効果的です。これにより、タプルの先頭要素（\(-score\)）が小さい順（＝元のスコアが大きい順）に並び、同点の場合は2番目の要素（参加者番号）が小さい順に自動的に並び替えられます。

ソート完了後、先頭から順に \(1, 2, \dots\) とシード番号を割り当てます。出力は元の参加者番号順（\(1\) から \(N\)）に行う必要があるため、あらかじめすべての要素を \(-1\) で初期化した長さ \(N\) の配列を用意し、該当する参加者の位置に求めたシード番号を書き込むことで、簡単に出力形式を満たすことができます。

アルゴリズム

1. 全要素が \(-1\) で初期化された、長さ \(N\) の結果用配列 ans を用意する。
2. 各参加者 \(i\) (\(0 \le i < N\), 0-indexed) について以下を行う：
   • 合計スコア \(S_i = A_i + B_i\) を計算する。
   • \(S_i \ge K\) ならば、リストにタプル (-S_i, i) を追加する。
3. リストを昇順にソートする。
4. ソート後のリストを先頭から順に走査し、順位（\(1, 2, \dots\)）を該当する参加者の位置 ans[i] に格納する。
5. ans の要素を順に改行区切りで出力する。

計算量

• 時間計算量: \(O(N \log N)\)
  • 本戦進出者の抽出に \(O(N)\)
  • 本戦進出者の人数を \(M\) (\(M \le N\)) とすると、ソートに \(O(M \log M) \le O(N \log N)\)
  • 結果配列の作成と出力に \(O(N)\)
  • 全体として \(O(N \log N)\) となり、\(N = 10^5\) でも制限時間内に余裕を持って処理できます。
• 空間計算量: \(O(N)\)
  • 進出者のリストおよび結果を保持する配列 ans のために \(O(N)\) のメモリを使用します。

実装のポイント

• 多基準ソートの簡潔な実装: 「ある値は降順、別の値は昇順」というソート順は、降順にしたい値にマイナスを掛けて昇順ソートを行うことで、1回のソート処理で簡潔に実現できます。

• 入出力の高速化: \(N\) の値が最大 \(10^5\) と大きいため、Pythonでは sys.stdin.read().split() による一括入力や、sys.stdout.write('\n'.join(...)) を用いた一括出力を行うことで、実行時間を大幅に短縮できます。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    K = int(input_data[1])
    
    qualifiers = []
    idx = 2
    for i in range(N):
        a = int(input_data[idx])
        b = int(input_data[idx+1])
        idx += 2
        s = a + b
        if s >= K:
            qualifiers.append((-s, i))
            
    qualifiers.sort()
    
    ans = [-1] * N
    for seed, (_, i) in enumerate(qualifiers, 1):
        ans[i] = seed
        
    sys.stdout.write('\n'.join(map(str, ans)) + '\n')

if __name__ == '__main__':
    main()

---

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