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

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

座標圧縮 (座圧)

テーマ解説記事 二分探索 二分探索:lower_bound 座標圧縮 前処理 Python ソート:前処理

競技プログラミングで時々問われる「座標圧縮」について簡単に解説します。

1. 座標圧縮とは

数列 A_{0}, A_{1}, \dots, A_{N-1} が与えられたときに、それぞれの要素が「全体の中で何番目に小さいか」を求めていく作業を、競プロ界では座標圧縮 (座圧) とよびます。

たとえば

A = (8, 100, 33, 12, 6, 1211)

に対しては、座標圧縮した結果は次のようになります。

1, 4, 3, 2, 0, 5

最も小さい数に「0」を割り当てて、小さい順に 1, 2, ... を割り当てて行っています。

同じ値があるとき

座標圧縮では、同じ値があるときは、タイは「一つの順位を占めるもの」として考えます。たとえば

A = (6, 9, 9, 2, 100)

に対しては、座標圧縮した結果は次のようになります。

1, 2, 2, 0, 3

コンテストの順位を決めるときのように

(間違い) 1, 2, 2, 0, 4

というようにはならないことに注意しましょう。タイは一つの順位に潰して考えます。

　

2. 座標圧縮の方法 (C++)

それでは、座標圧縮の方法を具体的に見ていきましょう。

座標圧縮の前処理

まず前処理として、数列 A_{0}, A_{1}, \dots, A_{N-1} をコピーして数列 B としておきましょう。そして、数列 B をソートします。さらに、 B から重複を除去します ( A が相異なる場合は省略可)。C++ ではたとえば次のように実装できます (Python3 は後述)。

ここでは具体例として、A = {8, 100, 33, 33, 33, 12, 6, 1211} という数列に対して前処理を行なっています。

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

int main() {
    // 座標圧縮したい数列
    vector<int> A = {8, 100, 33, 33, 33, 12, 6, 1211};

    // コピー
    vector<int> B = A;
    
    // B を小さい順にソート
    sort(B.begin(), B.end());
    
    // B から重複を除去する (A が相異なるときは省略可)
    B.erase(unique(B.begin(), B.end()), B.end());

    
    for (auto b: B) cout << b << ", ";
    cout << endl;
}

上の実装では最後に数列 B の中身を出力しています。その結果は次のようになります。

6, 8, 12, 33, 100, 1211,

もともとの数列 A の中身が、重複を除去して小さい順に並べたものになっていることがわかります。なお、ここまでの計算量は O(N \log N) です (数列 A のサイズを N とします)。

座標圧縮のメイン：二分探索法

以上の前処理で得られた数列 B に対して、次のことが言えます。

A_{i} が「全体の中で何番目に小さいか」とは、 A_{i} が「数列 B の何番目の要素に相当するか」を意味する

そしてこの答えは、二分探索法によって求められます。C++ であれば、std::lower_bound() が使えます。次のようにできます。

for (int i = 0; i < A.size(); ++i) {
    int ans = lower_bound(B.begin(), B.end(), a[i]) - B.begin();
}

ここで、lower_bound(B.begin(), B.end(), a[i]) とは、値が a[i] になるような配列 B 上のイテレータを返す処理を行っています。これから B の先頭のイテレータを返す B.begin() を引くことで、「a[i] が B の中で何番目の要素に相当するか」が求められます。

各 i に対して二分探索法によって O(\log N) の計算量でできますので、座標圧縮の計算量は O(N \log N) となります。前処理として数列 B を求める作業も O(N \log N) の計算量でできましたので、全体をとおした計算量も O(N \log N) となります。

まとめ

以上をまとめると、次のように実装できます。

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

int main() {
    // 座標圧縮したい数列
    vector<int> A = {8, 100, 33, 33, 33, 12, 6, 1211};

    // コピー
    vector<int> B = A;
    
    // B を小さい順にソート
    sort(B.begin(), B.end());
    
    // B から重複を除去する
    B.erase(unique(B.begin(), B.end()), B.end());

    // 座標圧縮した結果を求める
    vector<int> res(A.size());
    for (int i = 0; i < A.size(); ++i) {
        res[i] = lower_bound(B.begin(), B.end(), A[i]) - B.begin();
    }


    for (auto v: res) cout << v << ", ";
    cout << endl;
}

実行結果は、次のようになります。

1, 4, 3, 3, 3, 2, 0, 5,

　

3. Python3 の場合

Python3 では、二分探索法を用いる代わりに辞書型を用いた方がよいケースが多いようです。C++ では std::map 型の定数倍が遅いため、二分探索法を用いた方が高速ですが、Python3 では辞書型を用いるのが便利です。

次のように簡潔に実装できます。

# coding: utf-8

# 座標圧縮したい数列
A = [8, 100, 33, 33, 33, 12, 6, 1211]

# 集合型にすることで重複を除去し、
# 小さい順にソートする
B = sorted(set(A))

# B の各要素が何番目の要素なのかを辞書型で管理する
D = { v: i for i, v in enumerate(B) }

# 答え
print(list(map(lambda v: D[v], A)))

実行結果は次のようになります。

[1, 4, 3, 3, 3, 2, 0, 5]

　

4. 例題

座標圧縮の練習ができる例題をいくつか挙げます。

drken1215.hatenablog.com

最も典型的な座標圧縮の例題といえます。本当に座圧をするだけの問題ですので、動作確認に最適です。

　 drken1215.hatenablog.com

座標圧縮の例題として有名な ABC の過去問です。

　

5. 発展：二次元座標圧縮

多くの応用では、二次元平面上の N 個の点に対して座標圧縮をする場面も多々あります。

つまり、

(100, 674), (1, 76000), (50, 2), (10000, 16)

のような座標データを

(2, 2), (0, 3), (1, 0), (3, 1)

のようなデータに変換することを指します。このような処理を要求する例題としては次のようなものがあります。

drken1215.hatenablog.com