概要

合計スコアが \(K\) 点以上の参加者だけを取り出し、「合計スコアの降順、参加者番号の昇順」に並べます。その順番でシード番号を割り当て、参加者番号順に出力します。

考察

参加者 \(i\) の合計スコアを \(S_i = A_i + B_i\) とします。本戦に進出できるのは、\(S_i \ge K\) を満たす参加者です。

各参加者について、自分より優先される本戦進出者をすべて調べれば、シード番号を求められます。しかし、この方法では最悪で \(O(N^2)\) 時間かかり、\(N \le 10^5\) では間に合いません。

そこで、本戦進出者を優先順位どおりにソートすることを考えます。ソート後の先頭から \(1, 2, \dots\) と番号を付ければ、それがシード番号になります。

Pythonでは、タプルをソートすると、まず第1要素の昇順に並び、第1要素が同じ場合は第2要素の昇順に並びます。これを利用し、各本戦進出者を次の形で保存します。

(-total, i)

• 合計スコアにマイナスを付けることで、スコアが大きい参加者ほど先に並びます。
• 合計スコアが同じなら、参加者番号に対応する i が小さい参加者ほど先に並びます。

例えば、\(K = 100\) で、参加者 \(1, 2, 3, 4\) の合計スコアがそれぞれ \(120, 90, 150, 120\) の場合、本戦進出者の優先順位は次のようになります。

参加者番号	合計スコア	シード番号
\(3\)	\(150\)	\(1\)
\(1\)	\(120\)	\(2\)
\(4\)	\(120\)	\(3\)

参加者 \(1\) と \(4\) は同点なので、番号の小さい参加者 \(1\) が優先されます。参加者 \(2\) は本戦に進出しないため、答えは \(-1\) です。

なお、出力はシード番号順ではなく参加者番号順です。そのため、割り当てたシード番号は、元の参加者に対応する配列へ記録します。

アルゴリズム

1. 長さ \(N\) の配列 answers を、すべて \(-1\) で初期化します。
2. 各参加者について、合計スコア total = a + b を計算します。
   • total >= k なら、(-total, i) をリスト qualified に追加します。
   • それ以外の場合は何もしません。
3. qualified を昇順にソートします。
4. ソート後の先頭からシード番号 \(1, 2, \dots\) を割り当て、対応する answers[i] に記録します。
5. answers を先頭から順に、1行に1つずつ出力します。

ソート後の順番は、問題で指定された優先順位と一致しています。したがって、先頭から割り当てた番号は正しいシード番号です。また、本戦に進出しなかった参加者の値は初期値の \(-1\) のままなので、すべての参加者について正しい答えが得られます。

計算量

本戦に進出する参加者数を \(M\) とすると、入力の処理と出力に \(O(N)\)、ソートに \(O(M \log M)\) 時間かかります。\(M \le N\) より、最悪の場合の計算量は次のとおりです。

• 時間計算量: \(O(N \log N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 進出条件は「以上」なので、total >= k とします。合計スコアがちょうど \(K\) 点の参加者も本戦に進出します。

• コードでは参加者を \(0\) 始まりの添字 i で管理しています。実際の参加者番号は \(i+1\) ですが、大小関係は変わらないため、同点時の比較にもそのまま使えます。

• enumerate(qualified, 1) を使うと、シード番号を \(1\) から順に取得できます。

• 単に合計スコアの降順にするだけでなく、同点なら参加者番号の昇順という条件も満たす必要があります。(-total, i) を通常の昇順でソートすれば、両方を同時に実現できます。

• 本戦進出者が一人もいない場合も、answers がすべて \(-1\) のまま出力されるため、特別な処理は不要です。

  ソースコード

import sys


def main():
    input = sys.stdin.buffer.readline
    n, k = map(int, input().split())
    qualified = []
    answers = [-1] * n

    for i in range(n):
        a, b = map(int, input().split())
        total = a + b
        if total >= k:
            qualified.append((-total, i))

    qualified.sort()

    for seed, (_, i) in enumerate(qualified, 1):
        answers[i] = seed

    sys.stdout.write("\n".join(map(str, answers)))


if __name__ == "__main__":
    main()

---

この解説は gpt-6-astra-medium によって生成されました。