座標圧縮
通称「座圧」
茶色でも出る割にそれ以降でもかなりの頻度で要求されるし、時にはズルに使える強者。
使いどころ
定義域自体は非常に大きいが要素は現実的な個数しかない、みたいな値の集合を、定義域自体まで現実的な範囲に収めたい場合に使える
座圧して imos 法 を掛けたあと圧縮した分を復元するような問題もあった気がする 本来なら時間計算量$ Ο(N \leq 10^9)になるような計算について、上手く座標圧縮の考えを持ち込むと$ Ο(M \leq 2 \times 10^5)程度になる=$ M個の何らかの値があって、その値がある場所しか考えなくてよい、という問題がある 注意点
座圧においては基本的に$ A={6, 9, 7, 6, 4}から$ C={1, 3, 2, 1, 0}を得る。つまり、タイブレークはひとつの順位に潰される。その方が扱いやすい場合が非常に多い。
やり方
二分探索法
座圧したい配列を$ Aとし、$ |A| = Nとする。
1. まず、$ Aを昇順にソートして$ Bを得る。
2. $ Bから重複を排除する。ただし、タイブレークについてそれを$ 1つに潰さずにやる場合、つまり例えば$ A={6, 9, 7, 6, 4}から$ C={1, 4, 3, 1, 0}を得たい場合はこれを省略する。また$ Aの値が全て互いに相異なることが保証されているなら、この処理を省略してもよい。
3. $ Aを座圧した配列を$ Cに求めるとする。すると$ C_i = A_i が B_i 上で何番目の要素になったか？であり、これは二分探索を使うことで各要素につき $ Ο(\log N)で求められるため、総じて座標圧縮の計算量は$ Ο(N \log N)である。
ちなみに、2. の処理は C++ の場合
code:cpp
using namespace std;
// ↓が本題
b.erase(unique(all(b)), b.end())
上記のように、eraseとuniqueを用いることですぐに出来て、計算量も$ Ο(N^2)になったりはしないので、下手に色々とコードを書くよりはこれを使うことを推奨したい。
なお、この後はmapを使って座圧する方法が書いてあるが、C++ のmapはやたらと遅い。golang に大敗を喫するレベルで遅い。そのため C++ ユーザーは二分探索法を使うことを推奨する。二分探索もlower_boundで出来るし……
map 法
先程の二分探索の代わりにmapを用いることでも座圧が出来る。
具体的にはmap<int, int> = {値, 座圧後の値}というのを作ればよく、これは例えばPythonだと
code:python
B = {v: i for i, v in enumerate(sorted(set(a)))}
とすればよく、この場合$ Cは
code:python
このようなmapは、keyが昇順に並ぶようなものであればその性質を使って簡単に作ることが出来る。というのも
1. とりあえず$ Aの要素を全部map内にぶち込む。この時点でkeyは一意なので重複が排除できる
2. mapのkeyが昇順に並ぶことを前提として、keyを順番に参照して$ 0, 1, \ldotsと座圧後の値を割り振っていく。
これだけで座圧が出来てしまう。なお、mapのkeyが昇順に並ぶという制約上、$ Ο(N \log N)になるデータ構造がほとんどである、というか、keyが昇順に並ぶような$ Ο(N)のmapなんて多分ない。あったら大騒ぎになっているだろう。
にしても、この書き方だとPythonは結構速く座圧が出来るっぽい。
PyPyじゃない普通のPythonでやってみたが、C++で入出力高速化をせず律儀にendlで改行して出力する場合とだいたい一緒な速度になった。
ちなみに気を付けるべきこととして、JavaでいうHashMapとか、C++でいうunordered_mapを用いるとまともな結果にならない。C++のこれに関してはもう名前からして順番が保持されてないと言ってきてるし。
そのうちここのどっかのページにまとめたい気持ちがあるが、HashMapは$ Ο(1)で操作できる代わりに、格納されている値を順に取り出した時に昇順が保障されているとかは一切ない。TreeMapを使おう。
というか、C++はb.erase(unique(all(b)), b.end())という異常な書き方が出来るのが悪いのであって、だいたいの言語だとmapでやるのが普通かもしれない。
座圧する問題の例
実装の例
※この問題はジャッジの都合上、出力値の順番さえ正しければ、改行区切りの代わりに空白区切りを使ってもAC出来ます。
C++ のendlは出力されるたびに同時にstdoutのflushがかかるので、空白区切りにするとかなり高速化されます。え？\nを使え？打ちづらいからヤダ
C++
code:CoordinateCompression.cpp
using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
int main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n; cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++) cin >> ai; vector<int> b(all(a));
sort(all(b));
b.erase(unique(all(b)), b.end());
for(int i = 0; i < n; i++) cout << lower_bound(all(b), ai) - b.begin() << " "; cout << endl;
}
Java
code:CoordinateCompression.java
import java.util.*;
class CoordinateCompression{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
}
TreeMap<Integer, Integer> treeMap = new TreeMap<>();
for(int i = 0; i < n; i++) {
}
int ctr = 0;
for(var ent : treeMap.entrySet()){
treeMap.put(ent.getKey(), ctr);
ctr++;
}
for(int i = 0; i < n; i++){
System.out.print(treeMap.get(ai)); System.out.print(" ");
}
System.out.println();
sc.close();
}
}
※ コード長のことを考慮して通常の標準入出力を使っているので、速度に関してはお察しください。
空白区切りにしてもこの速度。恐ろしや。
ちなみにBufferedReader+StringTokenizerとPrintWriterを使うだけで$ 2.5倍も高速化されます。 Javaユーザ全員これやるべきだと思います。
Python
code:CoordinateCompression.py
n = int(input())
b = {v: i for i, v in enumerate(sorted(set(a)))}
Go
code:CoordinateCompression.go
package main
import (
"bufio"
"fmt"
"os"
"sort"
)
func min(a, b int64) int64 {
if a < b {
return a
} else {
return b
}
}
func max(a, b int64) int64 {
if a > b {
return a
} else {
return b
}
}
func main() {
r := bufio.NewReader(os.Stdin)
w := bufio.NewWriter(os.Stdout)
defer w.Flush()
var n int
fmt.Fscan(r, &n)
a := make([]int, n)
for i := 0; i < n; i++ {
}
keys := make([]int, len(m))
var idx int
for key := range m {
idx++
}
sort.Ints(keys)
var ctr int
for idx := range keys {
ctr++
}
for i := 0; i < n; i++ {
}
}