概要

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

典型的な「条件で絞り込み → 多重キーでソート → 順位付け」の問題です。

考察

重要な気づき

この問題で本質的に必要な情報は、各参加者の合計スコア \(S_i = A_i + B_i\) だけです。\(A_i\) と \(B_i\) を別々に持っておく必要はありません。

やるべきことは次の 3 つに分解できます。

1. \(S_i \ge K\) を満たす参加者（本戦進出者）を集める
2. 集めた参加者を「\(S_i\) が大きい順、同じなら \(i\) が小さい順」に並べる
3. 並べた順に \(1, 2, 3, \dots\) とシード番号を振り、元の参加者番号の位置に書き戻す

ここで注意したいのは、出力は「参加者 \(1\) から順に」求められている点です。ソートすると元の順番が失われてしまうので、参加者番号を一緒に持ち歩く必要があります。

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

「各参加者について、自分より優先される参加者が何人いるか数える」という方法を素直に実装すると、参加者ごとに全員を見るので \(O(N^2)\) になります。\(N \le 10^5\) なので \(10^{10}\) 回程度の比較が必要になり、確実に TLE します。

一方、ソートを使えば \(O(N \log N)\) で済み、\(10^5 \times 17 \approx 2 \times 10^6\) 程度なので余裕で間に合います。

オーバーフローへの注意

\(A_i, B_i \le 10^9\) なので \(A_i + B_i\) は最大 \(2 \times 10^9\) になります。これは 32bit 符号付き整数の上限 \(2147483647 \approx 2.1 \times 10^9\) に非常に近く、\(K \le 2 \times 10^9\) も同様です。ギリギリ収まるように見えますが危険なので、合計スコアと \(K\) は 64bit 整数（long long）で扱うのが安全です。Python なら気にする必要はありませんが、C++ / Java では要注意ポイントです。

具体例

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

\(i\)	\(A_i\)	\(B_i\)	\(S_i\)
1	50	60	110
2	30	30	60
3	70	40	110
4	90	90	180
5	10	90	100

本戦進出は \(S_i \ge 100\) の \(\{1, 3, 4, 5\}\)。これを優先順位で並べると

• \(S = 180\): 参加者 \(4\) → シード \(1\)
• \(S = 110\): 参加者 \(1\) と \(3\)（同点なので番号の小さい \(1\) が先）→ 参加者 \(1\) がシード \(2\)、参加者 \(3\) がシード \(3\)
• \(S = 100\): 参加者 \(5\) → シード \(4\)

参加者 \(2\) は落選なので \(-1\)。出力は上から 2, -1, 3, 1, 4 となります。

アルゴリズム

1. 入力を読みながら \(S_i = A_i + B_i\) を配列 s に格納する（\(0\)-indexed で持つと楽）。
2. \(S_i \ge K\) を満たす添字 \(i\) だけを集めたリスト idx を作る。
3. idx を次の比較関数でソートする。
   • \(S_x \ne S_y\) なら \(S_x > S_y\)（スコア降順）
   • \(S_x = S_y\) なら \(x < y\)（添字昇順）
4. 答え配列 ans を全て \(-1\) で初期化しておき、ソート後の idx を先頭から見て ans[idx[r]] = r + 1 とする。
5. ans を先頭から順に出力する。

ステップ 4 の「元の位置に書き戻す」操作がこの解法の要です。ソート結果の \(r\) 番目（\(0\)-indexed）にいる参加者のシード番号は \(r+1\) なので、それをその参加者の元の位置に代入します。

なお、ステップ 3 について、C++ の std::sort は安定ソートではありませんが、比較関数の中で同点時に添字の昇順を明示しているため問題ありません（安定ソート stable_sort を使うなら、添字の昇順で最初に並んでいる前提でスコア降順のみを比較条件にしてもよいです）。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的。入力読み込みと出力は \(O(N)\)）
• 空間計算量: \(O(N)\)（合計スコア配列、添字リスト、答え配列）

実装のポイント

• 64bit 整数を使う: \(A_i + B_i\) は最大 \(2 \times 10^9\)、\(K\) も最大 \(2 \times 10^9\) で 32bit 整数の限界付近です。C++ では long long、Java では long を使いましょう。

• 参加者番号を保持する: ソート対象を「値そのもの」ではなく「添字」にするのが簡潔です。vector<int> idx に添字を入れて、比較関数の中で s[x] を参照する形にすると、値と番号のペアを作らずに済みます。（pair<long long,int> に \((-S_i, i)\) を入れて昇順ソートする、という書き方も定番です。）

• 入出力の高速化: \(N \le 10^5\) 行の入出力があります。C++ で cin/cout を使う場合は ios::sync_with_stdio(false); cin.tie(nullptr); を書くか、コード例のように scanf を使いましょう。出力も 1 行ずつ printf するより、文字列バッファに溜めて最後に一度に書き出すと高速です。

• 全員が落選するケース: \(K\) が非常に大きく誰も進出しない場合、idx は空になりますが、ans が全て \(-1\) で初期化されているのでそのまま正しく動きます。特別扱いは不要です。

• \(K = 0\) のケース: 全員のスコアが \(0\) 以上なので、必ず全員が進出します。境界条件は「\(\ge K\)」（\(>\) ではない）ことに注意しましょう。

  ソースコード

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

int main(){
    int N; long long K;
    scanf("%d %lld", &N, &K);
    vector<long long> s(N);
    for(int i=0;i<N;i++){
        long long a,b; scanf("%lld %lld",&a,&b);
        s[i]=a+b;
    }
    vector<int> idx;
    idx.reserve(N);
    for(int i=0;i<N;i++) if(s[i]>=K) idx.push_back(i);
    sort(idx.begin(), idx.end(), [&](int x,int y){
        if(s[x]!=s[y]) return s[x]>s[y];
        return x<y;
    });
    vector<int> ans(N,-1);
    for(int r=0;r<(int)idx.size();r++) ans[idx[r]]=r+1;
    string out;
    out.reserve(N*8);
    for(int i=0;i<N;i++){
        out += to_string(ans[i]);
        out += '\n';
    }
    fputs(out.c_str(), stdout);
    return 0;
}

---

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