coordinate compression - 座標圧縮

アルゴリズムの概要

任意の配列の大きさの順序を保ったまま、その値を小さくする（圧縮する）

例えば、以下ののような配列があったとすると、座標圧縮によって のように値が小さくなる。

以下の手順で実現できる。

1. A を コピーして別のコンテナ（A'）に移し替える。 （a_dash = a でも、copy でもどちらでもよいと思う。）
2. A' を昇順にソートし、重複を排除する。（重複を排除するには、erase とunieque を組み合わせることで実現できる）
3. Aの各要素A[i] に対して、
   1. A[i] が A'のどの位置に存在するか、イテレーターを習得する。（ここでは二分探索（O(logN)）の lower_bond を使う）
   2. 取得したイテレーターを元に、添え字番号を取得する。（C++だと、itr - a.begin(); みたいな操作で添え字番号が取得できる）
   3. A[i] に 添え字番号を代入する

サンプル実装

#include <bits/stdc++.h>
#include <algorithm>

using namespace std;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define long long ll
#define all(a) (a).begin(), (a).end()

/**
 * cordinate compression - 座標圧縮
 * 関係性を保ったまま、値を小さくする操作の事
 * 
 * Order(N logN)
 * 
 * 例
 *  A = { 8, 3, 5, 2}
 *  A'= { 4, 2, 3, 1}
 * 
 * Aの順序を保ったまま、値だけを小さくしている
**/

int main()
{
    // 入力例を用意 
    vector<int> a{8, 3, 5, 2};

    // A をコピーして退避させる。
    vector<int> a_dash = a;

    // A' を昇順でソート
    sort(all(a_dash));

    // A' から重複した要素を削除する
    a_dash.erase(unique(all(a_dash)), a_dash.end());

    // Aの各要素A[i]に対して
    // A' にA[i] が存在する場合、そのイテレーターを取得する。
    // Aの最初の要素のイテレーターで引くと、圧縮された値を得ることができる。
    rep(i, a.size()) {
        a[i] = lower_bound(all(a_dash), a[i]) - a_dash.begin();
        cout << a[i] << " ";
    }
    cout << endl;
    return 0;
}

ABC 213 C - Reorder Cards の反省

atcoder.jp

この問題の肝は、縦と横。すなわちA[h]とB[w]が独立しており、A[h]に対して座標圧縮、B[w]に対して座標圧縮をすればいい。

そこまでは分かっていたが、肝心の、座標圧縮がかけずに敗退……。
（そもそも座標圧縮という言葉すら知らなかった笑　やろうとしていたことは近いと思う）

Submission #24884196 - AtCoder Beginner Contest 213

おおよそ同じようなことをしようとしていたのだが…、詰めが甘い部分が多い。

また、「読み込んだHとW使ってなくね？あれ、俺の考えているアルゴリズムは間違っている…？」と思って思考をこらせてしまったのがよくなかった。もっと自分の考えたアルゴリズムを信じるべきだった。

調べなおして、書き直した結果がこちら。
Submission #24901109 - AtCoder Beginner Contest 213