概要

各参加者の合計スコア \(A_i + B_i\) が \(K\) 以上の人だけを抽出し、「合計スコアの降順、同点なら参加者番号の昇順」に並べたときの順位（シード番号）を求める問題です。典型的な「複合キーによるソート」の練習問題です。

考察

重要な気づき

1. 前半戦・後半戦のスコアを個別に扱う必要はない
   本戦進出の判定も、シード番号の優先順位も、すべて合計スコア \(S_i = A_i + B_i\) のみで決まります。したがって入力を読んだ時点で \(S_i\) を計算してしまえば、以降は「値 \(S_i\) と番号 \(i\) の組」だけを考えればよくなります。

2. シード番号は「ソート後の並び順」そのもの
   本戦進出者を優先順位どおりに並べたとき、先頭から \(1, 2, 3, \dots\) と番号を振るだけで答えになります。「順位を計算する」という難しい処理は不要で、単に並べてから前から番号を振ればよいのです。

注意点として、同点の参加者がいても「同じ順位」にはなりません（シード番号は重複なく割り当てられる）。同点なら参加者番号が小さい方が先に来るので、タイブレーク（同点時の順序決定）を必ず参加者番号の昇順で行う必要があります。ここを忘れると、同点ケースで WA になります。

素朴なアプローチの問題

「各参加者について、自分より優先順位が高い進出者が何人いるかを数える」という定義通りの実装をすると、参加者ごとに全員を走査するため \(O(N^2)\) になります。\(N \le 10^5\) なので \(10^{10}\) 回程度の比較となり、確実に TLE です。

これは、そもそも「全員の順位」を一度に求めたいのだから、1 回ソートすれば全員の順位が同時に決まることに気づけば解決します。ソートは \(O(N \log N)\) で済みます。

元の位置を保持する工夫

ソートしてしまうと参加者番号の情報が失われるため、出力ができなくなります。そこで - 「(合計スコア, 参加者番号)」のペアをソートする、または - 「参加者番号（インデックス）の列」をスコアをキーにしてソートする

のいずれかにして、元のインデックスを持ち歩くのがポイントです。答えは ans[i] のような長さ \(N\) の配列に書き戻して、最後に \(1\) 行ずつ出力します。

具体例

\(N = 5\), \(K = 100\) で

\(i\)	\(A_i\)	\(B_i\)	\(S_i\)	進出？
1	50	60	110	○
2	30	40	70	×
3	100	20	120	○
4	60	50	110	○
5	0	0	0	×

進出者は \(\{1, 3, 4\}\)。優先順位順に並べると \(3 (120), 1 (110), 4 (110)\)（\(1\) と \(4\) は同点なので番号の小さい \(1\) が先）。よってシード番号は \(3 \to 1\), \(1 \to 2\), \(4 \to 3\) で、答えは順に 2, -1, 1, 3, -1 となります。

アルゴリズム

1. 入力を読み、各 \(i\) について \(S_i = A_i + B_i\) を計算する。
2. \(S_i \ge K\) を満たす参加者のインデックスだけを集めてリスト cand を作る。
3. cand を キー \((-S_i,\ i)\) の昇順（＝ \(S_i\) の降順、同点なら \(i\) の昇順）でソートする。
4. 長さ \(N\) の答え配列を \(-1\) で初期化し、cand の先頭から順に \(1, 2, 3, \dots\) を代入する。
5. 答え配列を先頭から出力する。

なお Python の sort は安定ソート（同じキーの要素の元の順序が保たれる）なので、cand を作った時点でインデックス昇順になっていることを利用して key=lambda i: -tot[i] だけでも正しく動きますが、意図を明示するために \((-S_i, i)\) をキーにするのが安全です。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的。入力の読み込みと \(S_i\) の計算は \(O(N)\)）
• 空間計算量: \(O(N)\)

実装のポイント

• オーバーフローの心配: \(A_i + B_i\) は最大 \(2 \times 10^9\) で 32bit 符号付き整数の範囲を超えます。C++ などでは long long を使ってください（Python は多倍長整数なので問題ありません）。\(K\) も最大 \(2 \times 10^9\) です。

• 降順ソートの書き方: Python では key にマイナスを付けて key=lambda i: (-tot[i], i) とするのが簡単です。「スコアは降順、番号は昇順」と方向が異なるため、単に reverse=True を付けると番号の順序が逆になってしまい WA になります。ここは要注意です。

• 入出力の高速化: \(N \le 10^5\) 行の入出力があるため、Python では sys.stdin.buffer.read().split() で一括読み込み、出力は "\n".join(...) でまとめて sys.stdout.write するのが安全です。input() と print() の繰り返しは遅くなりがちです。

• 境界条件: 判定は \(S_i \ge K\)（\(K\) 点「以上」）です。\(K = 0\) のときは全員進出、進出者が \(0\) 人のときは全行 -1 になります。等号の扱いを間違えないようにしましょう。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1])
    tot = [0] * n
    idx = 2
    for i in range(n):
        tot[i] = int(data[idx]) + int(data[idx + 1])
        idx += 2
    cand = [i for i in range(n) if tot[i] >= k]
    cand.sort(key=lambda i: (-tot[i], i))
    ans = [-1] * n
    r = 1
    for i in cand:
        ans[i] = r
        r += 1
    sys.stdout.write("\n".join(map(str, ans)))

main()

---

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