F - 番号付け / Numbering Editorial by physics0523
この問題には様々な解法が考えられます。
解法1. 上手くソートを利用する
この問題では、値のより小さい方により小さい値を、値が同じならより最初に出てくるものにより小さい値を割り当てることになります。
ここで、 (値, 場所) の組を以下の比較関数でソートすることを考えます。 ( 例えば \(A=(5,2,3)\) なら \((5,1),(2,2),(3,3)\) を並べ替えることを考えます )
- 値がより小さい方が先に来る。
- 値が等しいなら、場所がより小さい方が先に来る。
これは数列を辞書順ソートすれば実現される他、 C++ の場合では pair<int,int>
をデフォルトの比較関数で比較すれば上手くいきます。上手くソートできなさそうな言語の場合は比較関数やソートなどを自前で実装してください。
最後に、ソート後の配列について前から \(i\) 番目 (1-indexed) の要素の「場所」が \(j\) なら 答えのうち \(j\) 番目の要素に \(i\) を割り当てれば良いです。
実装例 (C++):
#include<bits/stdc++.h>
using namespace std;
using pi=pair<int,int>;
int main(){
int n;
cin >> n;
vector<int> res(n);
vector<pi> pv(n);
for(int i=0;i<n;i++){
cin >> pv[i].first;
pv[i].second=i;
}
sort(pv.begin(),pv.end());
for(int i=0;i<n;i++){
res[pv[i].second]=i+1;
}
for(int i=0;i<n;i++){
if(i){cout << " ";}
cout << res[i];
}cout << "\n";
return 0;
}
解法2. バケットソート風に処理する
ある値がどこに出てくるかという情報を全ての値について保持すればこの問題が解けそうなことが分かります。 例えば \(A=(2,7,1,8,2,8,1,8)\) なら
- \(1\) は \(3,7\) 番目に出てくる
- \(2\) は \(1,5\) 番目に出てくる
- \(7\) は \(2\) 番目に出てくる
- \(8\) は \(4,6,8\) 番目に出てくる
これを上手く管理することを考えます。
今回は \(A_i \le 10^9\) なので\(\max A_i\) 個の配列を用意するわけにはいきません。
そこで利用するのが連想配列 ( C++ では map
)です。
key を整数に、 value を整数の配列にしてやれば上手く使えそうです。 ( C++ では map<int,vector<int>>
)
これを実装に落とし込むと例のようになります。
実装例 (C++):
#include<bits/stdc++.h>
using namespace std;
using pi=pair<int,int>;
int main(){
int n;
cin >> n;
vector<int> res(n);
map<int,vector<int>> mp;
for(int i=0;i<n;i++){
int x;
cin >> x;
mp[x].push_back(i);
}
int cur=1;
for(auto &nx : mp){
for(auto &ny : nx.second){
res[ny]=cur;
cur++;
}
}
for(int i=0;i<n;i++){
if(i){cout << " ";}
cout << res[i];
}cout << "\n";
return 0;
}
posted:
last update: