複数の要素を基準にするソートについて

　先週、AtCoderのABC128に出ました。今回自分が初めて聞いた「bit全探索」を使う問題などがあり、全体的に難しく感じました。その分、反省点や得るものがありました。

　今回はB問題について書いていこうと思います。

考えたこと

　問題は「レストランがある市名と評価点数の二つの要素をもとに並び替えて、レストランの番号を出力せよ」でした。今回の難しかったポイントが市名は昇順に、点数は降順に並び替えるということです。

　コンテスト中では、2回それぞれを基準にしてバブルソートすればよいと気づきました。しかし普段からSTLのsort関数に頼っており、なかなか早く実装することができませんでした。反省を含め、復習したいと思います。

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;

int main(){
	int n;//店数.
	cin>>n;
	
	vector<string> s(n);//市名.
	vector<int> p(n);//評価点数.
	vector<int> num(n);//レストラン番号.
	
	for(int i=0;i<n;++i){
		cin>>s[i]>>p[i];
		num[i]=i+1;
	}
	
	for(int i=0;i<n-1;++i){//評価点数を基準にして降順にバブルソート.
		for(int j=n-1;j>i;--j){
			if(p[j-1]<p[j]){
				swap(s[j-1],s[j]);
				swap(p[j-1],p[j]);
				swap(num[j-1],num[j]);
			}
		}
	}	
	
	for(int i=0;i<n-1;++i){//市名を基準にして昇順にバブルソート.
		for(int j=n-1;j>i;--j){
			if(s[j-1]>s[j]){
				swap(s[j-1],s[j]);
				swap(p[j-1],p[j]);
				swap(num[j-1],num[j]);
			}
		}
	}
	
	for(int i=0;i<n;++i) cout<<num[i]<<endl;	
}

解説の解き方

　ところが解説では工夫をしてsort関数を使っていました。

　まず二つの要素をpairでくくり、そして並び替えたいint型の要素（string型では上手くいきませんでした.）に－１をかけるます。こうすることで全体の要素の大きさが逆転するので、二つの要素をまとめてsortしても題意の出力結果が求められるのです。

　（pairではfirstの要素を優先して並べ替えられるそうです。）

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;

int main(){
	int n;
	cin>>n;
	
	vector<pair<pair<string,int>,int> > v(n);
	for(int i=0;i<n;++i){
		string s;
		int p;
		cin>>s>>p;
		v[i]=make_pair(make_pair(s,-1*p),i+1);
	}
	
	sort(v.begin(),v.end());
	
	for(int i=0;i<n;++i){
		cout<<v[i].second<<endl;
	}
}//解説参考.

　基準にする複数の要素が別々に昇順降順にしたくても、このような工夫で解決できることには驚きました。

　（また、二重のpairも新鮮でした。３つ以上要素を囲みたい場合は「tuple」というものもあるようです。）

#皐月の平日の夕方