概要

\(N\) 人の参加者のうち合計スコアが \(K\) 点以上の人を抽出し、スコアの降順（同点なら参加者番号の昇順）に並び替えてシード番号を割り当て、最終的に元の参加者番号順に出力する問題です。

考察

本問では、以下の 2 つのステップを効率的に処理する必要があります。

1. 本戦進出者の抽出と順位付け
   • 条件 \(A_i + B_i \ge K\) を満たす参加者のみを集めます。
   • ルールに従って並び替えます（第1キー：合計スコアの降順、第2キー：参加者番号の昇順）。
2. 元の参加者番号順での結果の出力
   • 出力はシード番号順ではなく、「参加者 \(1\) の結果、参加者 \(2\) の結果、……」と番号順に行う必要があります。

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

各参加者 \(i\) について「自分よりスコアが高い（または同スコアで番号が小さい）進出者が何人いるか」を毎回全員と比較して数えると、1 人あたり \(O(N)\)、全体で \(O(N^2)\) の時間がかかってしまいます。 本問の制約は \(N \le 10^5\) であるため、\(O(N^2)\) の計算回数は約 \(10^{10}\) 回となり、実行時間制限に間に合わず TLE（実行時間制限超過）となります。

解決策

本戦進出者だけをひとつの配列にまとめ、ソート（並び替え） を利用します。 ソートを用いれば \(O(N \log N)\) で全体の順位を確定させることができます。順位が確定した後は、あらかじめ全要素を \(-1\) で初期化した配列（サイズ \(N+1\)）を用意し、各進出者の参加者番号のインデックスに対応するシード番号を書き込んでおくことで、最後に \(1\) 番から \(N\) 番まで順に出力するだけで \(O(N)\) で結果を出力できます。

アルゴリズム

1. 各参加者 \(i\) (\(1 \le i \le N\)) について、スコアの和 \(A_i + B_i\) を計算する。
2. \(A_i + B_i \ge K\) を満たす場合、「参加者番号 \(i\)」と「スコア \(A_i + B_i\)」の組を配列 qualified に追加する。
3. qualified を以下の優先順位に従ってソートする：
   • 合計スコアが異なる場合：合計スコアが大きい順（降順）
   • 合計スコアが同じ場合：参加者番号が小さい順（昇順）
4. ソート後の配列の先頭から順に、シード番号 \(1, 2, \dots\) を割り当てる。
   • 配列 ans を要素数 \(N + 1\)、初期値 \(-1\) で作成し、ans[進出者の番号] = シード番号 と記録していく。
5. \(i = 1, 2, \dots, N\) について ans[i] を順に出力する。

計算量

• 時間計算量: \(O(N \log N)\)
  • 進出者の人数を \(M\) (\(M \le N\)) とすると、ソートにかかる時間は \(O(M \log M) \le O(N \log N)\) です。
  • 入力の受け取り、進出判定、答えの出力はそれぞれ \(O(N)\) で行えるため、全体のボトルネックはソートの \(O(N \log N)\) となり、実行時間制限に余裕で間に合います。
• 空間計算量: \(O(N)\)
  • 進出者の情報を保持する配列や、各参加者のシード番号を記録する配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 変数の型（オーバーフロー対策）: スコア \(A_i, B_i\) は最大で \(10^9\) であり、合計スコアは最大 \(2 \times 10^9\) になります。32bit 符号付き整数の上限（約 \(2.14 \times 10^9\)）には収まりますが、オーバーフローの懸念をなくすために合計値や基準値 \(K\) には 64bit 整数型（C++ では long long など）を用いておくと安全です。

• ソートの比較条件: スコアは「大きい順（降順）」、番号は「小さい順（昇順）」と不等号の向きが逆になるため、比較関数（ラムダ式など）で条件の記述ミスがないよう注意しましょう。

• 入出力の高速化: 出力が最大 \(10^5\) 行に及ぶため、C++ では cin.tie(nullptr); ios::sync_with_stdio(false); を記述し、改行に std::endl ではなく "\n" を使用することで、入出力にかかる時間を大幅に削減できます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Participant {
    int id;
    long long score;
};

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

    int n;
    long long k;
    if (!(cin >> n >> k)) return 0;

    vector<Participant> qualified;
    qualified.reserve(n);

    for (int i = 1; i <= n; ++i) {
        long long a, b;
        cin >> a >> b;
        long long score = a + b;
        if (score >= k) {
            qualified.push_back({i, score});
        }
    }

    sort(qualified.begin(), qualified.end(), [](const Participant& x, const Participant& y) {
        if (x.score != y.score) {
            return x.score > y.score;
        }
        return x.id < y.id;
    });

    vector<int> ans(n + 1, -1);
    for (size_t i = 0; i < qualified.size(); ++i) {
        ans[qualified[i].id] = i + 1;
    }

    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << "\n";
    }

    return 0;
}

---

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