座標圧縮についての備忘録

競プロの精進をしていたら、座標圧縮というものに出くわした。
例えば、

{55,6,432,55,98,67,6,32};

のような配列を

{2,0,5,2,4,3,0,1};

の様に変換するものだ。

ゴリゴリやれば行けそうな気もするが上手いやり方があったのでそれを備忘録として残す。

手順を簡単に説明すると、

・元の配列aを、別の配列valsにコピー
・valsをソート
・valsから重複した要素を消す。
・配列aをなめて二分探索でvalsからインデックスを取得

といった具合だ。非常に上手い。

これをC++でコードに起こすと次のようになる。

vector<int> a{55,6,432,55,98,67,6,32};//元の配列

vector<int> vals=a;

sort(vals.begin(),vals.end());
auto itr=unique(vals.begin(),vals.end());//重複した要素を消す
//これだと消されたところが穴になる。
//unique()の戻り値は消されたところの次のイテレータ
vals.erase(itr,vals.end());//穴を消してあげる
for(auto aa:a){
	int ret=lower_bound(vals.begin(),vals.end(),aa) - vals.begin();
	cout<<ret<<" ";
}
cout<<endl;

ちなみに、

auto itr=unique(vals.begin(),vals.end());
vals.erase(itr,vals.end());

は、

vals.erase(unique(vals.begin(),vals.end()),vals.end());

の様に一つにまとめることもできる。

発見

新たに得られた知見としては、このアルゴリズム自体とunique()とerase()という関数の存在である。

余談だが、座標圧縮でコピー先の配列の変数名としてvalsを用いるのが慣例になっているようだがどういう意味なのだろうか。
あの「バルス！！」と関係あるのか、非常に興味がある。