今回の趣旨

今回は、競技プログラミングを学ぶ上で、真っ先に学ぶであろう "ソート" の基本的な使い方や、応用的な使い方を解説します。

この記事は、C++ を使用する人向けの記事となっています。

また、ソートの仕組みを学びたい場合は、こちらの記事をおすすめします。

ソートとは

ソートとは、 条件に従ってデータを並び替えること です。

例えば、小さい順に数値を並び替えるのなら、

ソート前

3 4 1 2 5

が、

ソート後

1 2 3 4 5

という風になります。

一般的に、ソートの計算量は $O(N \log N)$ です。

ソートは、計算量を改善するなどの目的で競技プログラミングでは多く使用されます。

ソートの基本

まずは、基本的なソートの実装方法を確認していきましょう。

ソートを使うには、STLの <algorithm> をインクルードする必要があります。(<bits/stdc++.h>でもok)

また、この記事では、using namespace std; を使用しています。
使用しないならば、std::sort, std::greater とする必要があります。

#include <algorithm>

昇順ソート

昇順ソート（小さい順でソート）を行うには、以下のような記述をします。

通常の配列では、 aを配列, nを配列の要素数とすると、

sort(a, a + n);

と書けます。

vector では、 aを配列とすると、

sort(a.begin(), a.end());

と書けます。

上のようなコードを実行することによって、
3 4 1 2 5 を 1 2 3 4 5 と並び替えることができます。

降順ソート

逆に、降順ソート（大きい順でソート）を行うには以下のような記述をします。

通常の配列では、

sort(a, a + n, greater<int>());

と書けます。
このコード例では、 greater<> の <> の中には int と書かれていますが、これは配列の型に合わせる必要があります。

vector では、

sort(a.rbegin(), a.rend());

と書けます。

上のようなコードを実行することによって、
3 4 1 2 5 を 5 4 3 2 1 と並び替えることができます。

一部のみのソート

一部のみをソートしたい場合はどのようにすればよいでしょうか。

配列で、a[0] と a[4] を除いたものをソートする場合、

sort(a + 1, a + n - 1);

と書けます。

vector でも、

sort(a.begin() + 1, a.end() - 1);

と書けます。

応用的なソート

さて、ここからがこの記事の山場です。

ここまでに学んだことでは、昇順・降順のどちらかでしかソートできません。
もっと複雑な条件でソートする方法を今から学びます。

まずは、試しに降順ソートを greater<int>,rbegin,rend を使わずに実装してみましょう。
どのように実装するのかというと、関数を使います。
ソートの第三引数に関数を渡すことによって実装できます。

実装例1

  auto func = [](int a, int b){
    return a > b;
  };
  
  sort(a.begin(), a.end(), func);

実装例2

  sort(a.begin(), a.end(), [](int a, int b){
    return a > b;
  });

このように記述することによって、降順ソートは実装できます。

実装例2 は、ソートの第三引数に直接関数を記述しているだけで、実装例1 と内容は変わりません。

return a > b; が true なら a は左側に移動して、 false なら a は右側に移動するというイメージです。

次は、5 に近い順でソートしてみましょう。

これは、あなたが実装してみましょう。

実装例

  sort(a.begin(), a.end(), [](int a, int b){
    return abs(5 - a) <= abs(5 - b);
  });

(<= の部分は、多少違っていても大丈夫です。)

ここからは、問題を解いてみましょう。

ABC201 B - Do you know the second highest mountain?

AtCoder国には $N$ 個の山があり、$i$ 個目の山の名前は $S_i$ で、高さは $T_i$ です。
2 番目に高い山の名前を答えてください。
$N$ 個の山の名前、高さはそれぞれ相異なることが保証されます。

この下には解説・解答があります。

まず、山の名前と高さを pair で記録しておきます。
このときに、ソートしやすいように山の高さを first に記録しておきましょう。
（pair をソートするときは、 first の大小が優先されます。)

そして、山の名前と高さを記録したら、ソートをします。
2番目に高い山の名前を答えるので、降順ソートにしましょう。

そして、ソートをしたら、2番目に高い山の名前を出力しましょう。

この方法でこの問題は解くことができます。

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

signed main(void){
  int n;
  cin >> n;
  vector<pair<int, string> > a(n);
  for(int i = 0; i < n; i++){
    cin >> a[i].second >> a[i].first;
  }
  //読み込む
  
  sort(a.rbegin(), a.rend());
  //降順にソートする
  
  cout << a[1].second << endl;
  //2番目に高い山の名前を出力する
}

ABC219 C - Neo-lexicographic Ordering

AtCoder 王国を治める高橋君は、英小文字のアルファベット順を変更することにしました。
新たなアルファベット順は a , b ,…, z を並べ替えて得られる文字列 X を用いて表されます。
X の $i(1≤i≤26)$ 文字目は、新たな順番において $i$ 番目に小さい英小文字を表します。
AtCoder 王国には $N$ 人の国民がおり、それぞれの国民の名前は $S_1,S_ 2,…,S_N$です。
ここで、$S_i(1≤i≤N)$ は英小文字からなります。
これらの名前を、高橋君の定めたアルファベット順に基づく辞書順に従って並べ替えてください。

この問題は、$N$個の文字列を並び替えればよいが、アルファベット順が変更されているので、通常のソートでは正しく並べ替えられません。

なので、アルファベット順の変更に対応したソートを実装します。
入力例1 を例に考えてみましょう。

入力例1

bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa

まず、一番上の文字列から、 b は a よりも小さく、 a は c よりも小さいなどの情報がわかります。
上の文字列から、 map を使って、どの文字は何番目に小さいかを記録します。
例えば、 map[b] = 1, map[a] = 2, map[c] = 3; となります。

そして、その map を使って特殊なソートを実装します。

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

signed main(void){
  string x;
  int n;
  cin >> x >> n;
  string s[n];
  for(int i = 0; i < n; i++) cin >> s[i];
  map<char,int> pos;
  
  for(int i = 0; i < 26; i++){
    pos[x[i]] = i + 1;
    //pos という map に、 x[i] が辞書順で何番目か記録しておく
  }
  
  sort(s, s + n, [&](string a, string b){
    for(int i = 0; i < (int)min(a.size(), b.size()); i++){
      int aa = pos[a[i]], bb = pos[b[i]];
      
      if(aa != bb) return aa < bb;
      //特殊なアルファベット順でどちらが小さいかを比較する
    }
    
    return a.size() < b.size();
    //どの文字も同じだった場合は、長さで判断する
  });
  
  for(int i = 0; i < n; i++){
    cout << s[i] << endl;
  }
}