概要

本戦に進出する参加者だけを取り出し、「合計スコアの降順、参加者番号の昇順」に並べます。その順にシード番号を付け、参加者番号順に答えを出力します。

考察

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

各参加者について、自分より優先される参加者の人数を全員と比較して数える方法も考えられます。しかし、この方法では時間計算量が \(O(N^2)\) となり、\(N \le 10^5\) では時間制限に間に合いません。

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

優先順位は次のとおりです。

• 合計スコアが大きい人が先。
• 合計スコアが同じなら、参加者番号が小さい人が先。

コードでは、この順序を実現するために \((-S_i, i)\) というペアを保存しています。ペアを昇順にソートすると、まず第1要素が比較され、同じ場合に第2要素が比較されます。

スコアを負にすると、スコアが大きいほど第1要素は小さくなるため、通常の昇順ソートで目的の順序を作れます。

例えば、\(K = 100\) で合計スコアが次のようになっているとします。

参加者番号	合計スコア
1	120
2	90
3	150
4	120

本戦進出者の順序は、参加者 \(3, 1, 4\) です。参加者 \(1\) と \(4\) は同点なので、番号の小さい参加者 \(1\) が先になります。

したがって、参加者番号順の答えは \(2, -1, 1, 3\) となります。

アルゴリズム

1. 答えを保存する配列 answer を用意し、すべての要素を \(-1\) で初期化します。
2. 各参加者の合計スコア \(S_i = A_i + B_i\) を計算します。
   • \(S_i \ge K\) なら、qualified に \((-S_i, i)\) を追加します。
   • \(S_i < K\) なら追加しません。
3. qualified を昇順にソートします。
4. ソート後の \(j\) 番目（\(0\) 始まり）の参加者に、シード番号 \(j+1\) を割り当てます。
   • 元の参加者番号に対応する answer の要素に保存します。
5. answer を先頭から順に出力します。

ソートによって本戦進出者は問題の優先順位どおりに並ぶため、先頭から割り当てた番号は正しいシード番号です。また、本戦に進出しない参加者の答えは初期値の \(-1\) のままなので、すべての参加者について正しい結果が得られます。

計算量

本戦進出者数を \(M\) とすると、入力と出力に \(O(N)\)、ソートに \(O(M \log M)\) かかります。\(M \le N\) より、全体の計算量は次のとおりです。

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

実装のポイント

• 進出条件は「以上」なので、A + B >= K と判定します。

• 同点でもシード番号は重複させません。 同点の参加者は参加者番号順に並べ、それぞれ異なる番号を付けます。

• 出力順はシード番号順ではなく、参加者番号順です。 ソート時に元の参加者番号を保持し、answer の対応する位置へ結果を書き込みます。

• コード内の参加者番号は \(0\) 始まりですが、番号の大小関係は変わらないため、そのまま比較に使えます。シード番号は \(1\) 始まりなので、ソート後の位置に \(1\) を足します。

• 合計スコアは最大 \(2 \times 10^9\) です。コードではスコアやその負数を余裕を持って扱えるよう、long long を使っています。

• 本戦進出者が \(0\) 人でも、answer はすべて \(-1\) のままとなり、特別な場合分けは不要です。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long K;
    cin >> N >> K;

    vector<pair<long long, int>> qualified;
    qualified.reserve(N);
    vector<int> answer(N, -1);

    for (int i = 0; i < N; ++i) {
        long long A, B;
        cin >> A >> B;
        if (A + B >= K) {
            qualified.emplace_back(-(A + B), i);
        }
    }

    sort(qualified.begin(), qualified.end());

    for (int i = 0; i < static_cast<int>(qualified.size()); ++i) {
        answer[qualified[i].second] = i + 1;
    }

    for (int seed : answer) {
        cout << seed << '\n';
    }

    return 0;
}

---

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