AtCoder ABC 036 C - 座圧 (試験管緑色)

文字通り、与えられた数列を座標圧縮する問題ですね。

• 問題へのリンク

問題概要

長さ の数列 が与えられます。

これらの数列から重複を除外して小さい順に並び直して得られる数列を とします。

各 に対して、 となるような を出力してください。

制約

• 

座標圧縮

まさに座標圧縮をしてください、という問題です！！

drken1215.hatenablog.com

座標圧縮については上の記事に詳しく書きました。ここでは C++ と Python でのコード例を載せます。いずれも計算量は となります。

コード例 (C++)

#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];

    // 座圧準備
    auto B = A;
    sort(B.begin(), B.end());
    B.erase(unique(B.begin(), B.end()), B.end());

    // 座圧
    for (auto a: A) {
        cout << lower_bound(B.begin(), B.end(), a) - B.begin() << endl;
    }
}

コード例 (Python3)

# 入力
N = int(input())
A = [int(input()) for _ in range(N)]

# 辞書をつくる
D = { v: i for i, v in enumerate(sorted(set(A))) }

# 答え
for a in A:
    print(D[a])