けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 春合宿 2007 day1-1 Score (難易度 3)

まさに「座標圧縮」をしてください、という問題!

問題概要

 N 個の整数  A_{1}, \dots, A_{N} が与えられる。それぞれについて、「大きい順に何番目か」を求めよ。

たとえば  A = (100, 90, 80, 90, 100, 65) に対しては、答えは  (1, 3, 5, 3, 1, 6) となる。

制約

  •  1 \le N \le 10^{5}
  •  0 \le A_{i} \le 100

前提知識

座標圧縮について知っておきましょう!

drken1215.hatenablog.com

考えたこと

今回の問題のように、小さい順または大きい順に番号付けするのは、ぞくに「座標圧縮」と呼ばれる。より難しい問題の前処理として頻繁に登場する。本来の座標圧縮では、タイは除外する (上の例では 90 と 100 のタイは除外して  (1, 2, 3, 2, 1, 4) とする) ことが多いのでちょっと違うけど...。

さて、「大きい順」というのが考えづらいので、あらかじめ  A の各要素に対して

A[i] = 100 - A[i];

とすることにする。こうすれば「小さい順に何番目か」という問題になって扱いやすくなる。その後は次のようにする。


  •  A を小さい順にソートした配列を  S とする
  • A[i] に対して lower_bound(S.begin(), S.end(), A[i]) - S.begin() を求める

これで求められる。ただしこのままでは 0-indexed なので 1-indexed に直して出力する。計算量は  O(N \log N)

コード

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

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i], A[i] = 100-A[i];
    auto S = A;
    sort(S.begin(), S.end());

    for (int i = 0; i < N; ++i) {
        int res = lower_bound(S.begin(), S.end(), A[i]) - S.begin();
        ++res;
        cout << res << endl;
    }
}