アルゴ式 「ソートアルゴリズム」まとめ

# これは何?
[アルゴ式](https://algo-method.com)にある問題を解いた個人的なまとめ。
それの[ソートアルゴリズム](https://algo-method.com/lecture_groups/18)編。

開発側の人達が頑張って問題ごとに解説を書いてくれているが、まだ解説のない問題の穴埋めになればと思って書いている。
解法は自明なものが多いのでおそらくそこまで意味はない。

# 目次
目次です。

|タイトル|求められるもの|
|-------|-------------|
|[中央値](https://algo-method.com/tasks/501)|ソート|
|[X番目に小さな値](https://algo-method.com/tasks/489)|ソート|
|[総和の最大値](https://algo-method.com/tasks/484)|降順ソート、貪欲法|
|[差の最小値](https://algo-method.com/tasks/490)|ソート、最小値|
|[テストの順位](https://algo-method.com/tasks/492)|ソート、(座標圧縮?)|
|[投票結果](https://algo-method.com/tasks/502)|ソート、(タプル?)|
|[順位表の並び替え](https://algo-method.com/tasks/493)|ソート、タプル|
|[ごはんを買う](https://algo-method.com/tasks/491)|ソート、貪欲法|

たまに独自関数を使っていることがあって、そのときはmain関数の前に独自関数を書いてます。
適宜参照してください。

# 中央値
基本です。
問題文のとおりに書けば良いです。
Pythonなら割り算後の値は勝手に小数にしてくれるのですが、C++は整数型で割り算をすると切り捨て除算になるため、doubleにキャストしてあげる必要があります。
あと、coutで値を出力するときにfixedをつけることとsetprecisionを適当に大きな値にしてあげる必要があります。

これらは```iomanip```ヘッダーにあります。(GCCの人やアルゴ式のように\<bits/stdc++.h\>が使える環境の人は気にしなくてもいいです。自分AtCoderとかでもbits/stdc++を使わないので気にしています。)

```c++:中央値
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

void setfixed(){
    cout << fixed << setprecision(12);
}

void fastio(bool is_fixed){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (is_fixed) setfixed();
}

int main() {
	fastio(true);

    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto &x : a) cin >> x;
    sort(a.begin(), a.end());

    if (n%2 == 0){
        cout << double(a[(n/2)-1]+a[n/2])/double(2) << endl;
    }
    else{
        cout << a[n/2] << endl;
    }
}
```

# X番目に小さな値
これも基本です。
基本というか、ソートをする目的みたいな感じです。
一番小さい数が1として入力されることが多いのですが、この問題では一番小さい数を0としているので$X_k$をindexとしてそのまま出力すればよいです。

もし一番小さい数が1として入力される場合は当たり前ですが1を引いてindexとして用いればよいです。

```cpp:X番目に小さな値
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

template <typename T> T nextval(){T buf; cin >> buf; return buf;}

int main() {
	int n, m;
    cin >> n >> m;
    vector<ll> a(n);
    for (auto &x : a) cin >> x;
    sort(a.begin(), a.end());
    
    for (int i = 0; i < m; i++) cout << a[nextval<int>()] << endl;
}
```

# 総和の最大値
すこし考えることが出てくる問題です。
できるだけ総和が大きくなるように数字を選ぶので、わざわざ小さな数字を選ぶ必要はないです。

例えばある数列$\lbrace A\rbrace = \lbrace 1, 3, 6, 8 \rbrace$から1つだけ数字を選ぶことができるとします。選んだ数字の最大値はいくつですか?と考えたとき、小さな数字を選ぶ理由はなく、8を選んで良いです。

したがって、与えられた数字を降順ソートして一番最初に来た数(与えられた中で一番大きな数)から$k$個選べば良いです。

C++で降順ソートするときは主に

```cpp
sort(a.begin(), a.end(), greater<T>());
```
を使うと思うのですが、これを以下のように書くことができます。

```cpp
sort(a.rbegin(), a.rend());
```
リバースイテレーターを用いることで完結に書くことができます。

```cpp:総和の最大値
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main() {
	int n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (auto &x : a) cin >> x;
    sort(a.rbegin(), a.rend());

    ll ans = 0;
    for (int i = 0; i < k; i++) ans += a[i];

    cout << ans << endl;
}
```

# 差の最小値
こちらも少し考える問題です。
まず、問題から連続する$K$個の整数を選ぶわけではないので入力の順序は関係ないということがわかります。
したがって入力をソートしてしまって良いです。

ここでソートをする理由は差の最小値を考えたいのでできるだけ値が近い入力同士を隣接させたいからです。
こうすることで適当に$K$個選んで差の最小値を達成する問題から、ソート済みの数列$\lbrace A\rbrace$から連続する$K$個の値を選んで$A_{i+K-1}-A_i$の最小値を探す問題に帰結することができます。

また、この数列はソート済みなので必ず$A_i < A_{i+1}$が成り立ちます。
よって、差を考えるときに変に総当りをして差の絶対値を取る必要がないです。
こういう意味でもソートしておくことで問題の「良い性質」を利用できます。

最初差の最小値は大きな値で初期化しておくと良いです。(よくよく考えたら$2e18$ほど大きくなくてよかったです。$3e9$くらいで十分です。)

```cpp:差の最小値
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main() {
	ll n, k;
    cin >> n >> k;
    vector<ll> a(n, 0);
    for (auto &x : a) cin >> x;

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

    ll diff = 2e18;
    for (ll i = 0; i <= n-k; i++) diff = min(diff, a[i+k-1]-a[i]);

    cout << diff << endl;
}
```

# テストの順位
これ、解説側の想定解があれば見たかったのですが一体どうすればよかったのでしょう。
他の人の回答いわくPythonだとかなりきれいに解けるらしいのですが、私のC++スキルが低すぎるばかりに簡潔な記述ができませんでした。

私の回答を基準に説明すると座標圧縮という操作を行うと良いです。
つまるところ登場した数字は登場した数字の一番小さい方から何番目?というのを高速に求める(そこまで高速ではないが)操作のことです。
ただし、ここでは高得点者がより上位になるため素直に座標圧縮をすると低得点者がより上位になってしまいます。
そこで、重複を省いた点数の種類数-1を持っておいて、それから座標圧縮されたリストのindexを引くことで高得点者がより早い番号に、低得点者は遅い番号に直すことができます。

C++のlower_bound(二分探索)関数が返すのはindexではなくイテレーターなので探索したリストのbegin()イテレーターを引くことでintにキャストしておきましょう。

```cpp:テストの順位
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main() {
	int n;
    cin >> n;
    vector<ll> a(n);
    for (auto &x : a) cin >> x;

    vector<ll> score = a;
    sort(score.begin(), score.end());
    score.erase(unique(score.begin(), score.end()), score.end());

    int k = score.size()-1;
    for (auto x : a){
        cout << k-(lower_bound(score.begin(), score.end(), x)-score.begin()) << endl;
    }
}
```

# 投票結果
正直イヤなタイプの問題です。
どこがイヤかというとソートが複雑です。

具体的には生徒が得た票は降順でソートしたいですが生徒番号は昇順でソートしたい。という次元によってソート基準を変える必要があるのがこの問題の嫌なところです。

似たような問題がABCで出題されていた([ABC222 - Swiss System Tournament](https://atcoder.jp/contests/abc222/tasks/abc222_c))こともあり、それが解けなかった苦い思い出もあり、なんとなくこれの解き方はわかりました。

要は、ソート基準をどちらかに揃えてあげるとかんたんに解くことができます。
例えば、どちらも昇順ソートして問題を解決するには得た票の値が大きな値であるほど小さな値に、小さな値はその反対に変換してあげればいいわけです。それをする方法は意外と単純で票数に-1をかけてあげると良いです。

これでソート自体は上手くいきます。
ただし、マイナスの値で出力してはいけないので出力時に-1をかけるのを忘れないでください。

```cpp:投票結果
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main() {
    int n;
    cin >> n;
    vector<pair<ll, ll>> candidate(n);

    for (int i = 0; i < n; i++){
        candidate[i].second = -i;
        candidate[i].first = 0;
    }

    for (int i = 0; i < n; i++){
        ll voted; cin >> voted;
        candidate[voted].first++;
    }

    sort(candidate.rbegin(), candidate.rend());
    for (int i = 0; i < n; i++){
        cout << candidate[i].second*-1 << " " << candidate[i].first << endl;
    }
}
```
pair型という型を使うことでかなり簡潔に記述できます。

また、C++はstd::sortに独自のソート関数を渡すことができるのでそれを使って解いても良いです。
確か先程のSwiss System Tournamentでも独自のソート関数で解いていた人がいたような気がします。

# 順位表の並び替え
投票結果の応用問題です。
ソート対象となる次元が更に増えました。

が、増えたならそれを同時に管理できる形を呼んであげればよいです。
C++にもタプルと呼ばれる型があり、3つ以上の型でもいい感じに同時に扱うことができます。
ただし、pair型のようにfirst, secondときてthirdとなるわけではなく、タプルの中の変数を直接イジれるわけではないのでそこには馴れないといけません。

今回も数学の入力に-1をかけていい感じにソートしていきます。

```cpp:順位表の並び替え
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main() {
	//名前は別、数学は-1をかけた値。合計点はそのまま。もともとの順位番号は最後に入れる

    ll n; cin >> n;
    vector<string> s(n);
    //1 - math*-1, 2 - english, 3 - number
    vector<tuple<ll, ll, ll>> table(n);
    for (int i = 0; i < n; i++){
        string si; int ai, bi;
        cin >> si >> ai >> bi;
        s[i] = si;
        table[i] = make_tuple(ai*-1, ai+bi, i);
    }

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

    for (int i = 0; i < n; i++){
        auto [ai, bi, ci] = table[i];
        cout << s[ci] << " " << ai*-1 << " " << bi-(ai*-1) << endl;
    }
}
```

# ごはんを買う
これもまた貪欲法で解けます。
$K$個ご飯を買うまでの最小金額を求めたいので、贅沢して高いごはんを買う必要はないです。
安いのを買えるだけ、満足するまで買えばよいです。

ただ、まともに1個1個選んでるとTLE(実行制限時間超過)するので安いやつを大人買いすると計算量が$O(K)$から$O(N)$まで落ちるので十分高速に動作します。(一回成約みてなくてTLEしちゃった...)

大人買いにも少し工夫が必要で、$K$個以上誤って購入してしまうことがあるのでそこだけ注意が必要です。
$K$が0になるまで買えばよいので、$i$番目の商品を在庫だけ買ったとして、後の$K$の値が0以上ならその商品を全部買う。
-1以下になってしまうなら$K$個だけその商品を買います。

```cpp:ごはんを買う
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main() {
	ll n, k;
    cin >> n >> k;
    vector<pair<ll, ll>> a(n);
    for (int i = 0; i < n; i++){
        cin >> a[i].first >> a[i].second;
    }

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

    ll ans = 0;
    ll index = 0;
    while(k){
        if (k-a[index].second > -1) ans += (a[index].first)*a[index].second;
        else ans += (a[index].first)*k;
        k=max(k-a[index].second, 0LL);
        index++;
    }

    cout << ans << endl;
}
```