座標圧縮をばっこり解説 [競プロ]

座標圧縮とは

座標関係なく、数値の大小関係のみが重要な時に、軽量化するために用いる処理のことです。

サンプルコード

coordinate_compression.cpp

void solve() {
    // 入力待ち
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i) cin >> v[i];

    // 代行を作成 → 昇順に並び替え → 重複消去 → 元のベクトルを書き換え
    vector<int> p = v;
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    for (int& x : v) x = lower_bound(p.begin(), p.end(), x) - p.begin();

    // 結果出力
    for (int i = 0; i < n; ++i) cout << "v[" << i << "]: " << v[i] << endl;
}

実例

鉄則本A15
この問題はデータの軽量化というよりは、座標圧縮をしたものを出力しなさいという感じですが、基本なのでよいと思います。実装例
ABC213C問題
この問題は上の問題の2次元版です。実装例

(追記募集しています。編集リクエスト通します。)

まとめ

正直理解が正しいか怪しいです。
何かご指摘ございましたら、コメント欄にてお願いいたします。
それでは！