ABC036 座圧 - chacoderのブログ

ABC036

　大小関係を保持したままデータを圧縮する操作を座標圧縮（座圧）と呼ぶようです。

けんちょん本６章の章末問題6.1にでてきましたが、まだ解説がないので自分で考えてみました。座圧でぐぐったらABC036がでてきて、これはまさに座圧でした。

素朴なアルゴリズム

Pair配列とsort関数を使って素朴に書いてみました。

とりあえずはABC036Cぐらいの制約ならACできますが実行速度が181msとやや遅く、提出例を見ていると40ms前後のコードや最短では7msのコードがありました。

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

int main(){
int n;
cin>>n;
vector<pair<int,int>>P;
for(int i=0;i<n;i++){
int temp;
cin>>temp;
P.push_back({temp,i});
}
sort(P.begin(),P.end());
int cnt=0;
ans[0]=cnt;
for(int i=1;i<n;i++){
if(P[i].first==P[i-1].first){
ans[P[i].second]=ans[P[i-1].second];
}
else{
cnt++;
ans[P[i].second]=cnt;
}
}
for(int i=0;i<n;i++){
cout<<ans[i]<<endl;
}
return 0;
}

二分探索を使った高速化

解説では連想配列mapを使ったアルゴリズムが推奨されていました。
mapを使えばちょっと書きやすいかも知れませんが、素朴なアルゴリズムとそんなに差はなさそうです。

けんちょん本では二分探索を使ってО（ＮlogN）で書くことを求められています。

まず配列をソートした上で、ソート前の配列の最初のやつから、配列の中で大きさで何番目のデータかを二分探索で求めて順に出力していくというアルゴリズムを思いつきます。

実装にトライ

とりあえず立てた方針で書いてみましたがうまくありません。
同じデータが複数あった場合に配列の先頭からの距離での出力だとちとまずい。

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

int main(){
  int n;
  cin>>n;
  vector<int>A(n,0);
  vector<int>B(n,0);
  for(int i=0;i<n;i++){
    cin>>A[i];
    B[i]=A[i];
  }
  sort(B.begin(),B.end());
  for(int i=0;i<n;i++){
    cout<<lower_bound(B.begin(),B.end(),A[i])-B.begin()<<endl;
  }
  return 0;
}

mapを使った実装

重複データをまとめて種類を数えるならmapだろうということで、改めてmapを使って実装。
ACするものの速度はあまり早くない。

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

int main(){
  int n;
  cin>>n;
  vector<int>A(n,0);
  map<int,int>mp;
  
  for(int i=0;i<n;i++){
    cin>>A[i];
    mp[A[i]]++;
  }
  
  int cnt=0;
  for(auto &p:mp) p.second=cnt++;
  for(int i=0;i<n;i++) cout<<mp[A[i]]<<endl;
  return 0;
}

二分探索をどう使うか

重複データを削除したソート済みの配列を準備して二分探索を使うことを考えます。

vectorから削除する際にデータの前の方を消すと後ろがおかしくなるみたいで、後ろから消していくことにしました。

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

int main(){
  int n;
  cin>>n;
  vector<int>A(n,0);
  vector<int>B(n,0);
  for(int i=0;i<n;i++){
    cin>>A[i];
    B[i]=A[i];
  }  
  sort(B.begin(),B.end());
  for(int i=n-1;i>0;i--){
    if(B[i-1]==B[i]){
      B.erase(B.begin()+i);
    }
  }
  for(int i=0;i<n;i++){
    cout<<lower_bound(B.begin(),B.end(),A[i])-B.begin()<<endl;
  }  
  return 0;
}

ACしましたがこれもあまり早くなく、無理やり二分探索使っただけみたいになってしまいました。
配列が大きな場合には多少早くなるかも知れません