【競プロTips】配列をするソート前に各値に-1をかけてソートすることで降順ソートを実現する

結論

数値の配列を降順にソートしたいとき、各値に-1をかけてからソート。その後各値に-1をかけて復元することで降順ソートを実現できます。pairをソートするときなどに便利です。

解説

有名なテクニックだとは思いますが、記事としてまとめます。
通常、配列¹をソートすると昇順にソートされます。

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

int main(){
    vector<int> v{23, 42, 33, 32, 23, 21, 74, 67, 70, 63};
    
    cout << "ソート前: ";
    for(int elm : v) {
        cout << elm << " ";
    }
    cout << endl;
    
    sort(v.begin(), v.end());
    
    cout << "ソート後: ";
    for(int elm : v) {
        // 昇順で出力される
        cout << elm << " ";
    }
    cout << endl;
    
    return 0;
}

ソート前: 23 42 33 32 23 21 74 67 70 63 
ソート後: 21 23 23 32 33 42 63 67 70 74 

これを、ソート前に各値に-1をかけてからソートすることで値の順番が逆転します。各値同士の大小関係が入れ替わるためです。

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

int main(){
    vector<int> v{23, 42, 33, 32, 23, 21, 74, 67, 70, 63};
    
    cout << "ソート前: ";
    for(int elm : v) {
        cout << elm << " ";
    }
    cout << endl;

    // 各値に-1をかける
    for(int &elm : v) {
        elm *= -1;
    }
    
    sort(v.begin(), v.end());
    
    cout << "ソート後: ";
    for(int elm : v) {
        // 順番が逆転する
        cout << elm << " ";
    }
    cout << endl;
    
    return 0;
}

ソート前: 23 42 33 32 23 21 74 67 70 63 
ソート後: -74 -70 -67 -63 -42 -33 -32 -23 -23 -21 

あとはソート後の値にもう一度-1をかけて元の値を復元すれば降順にソートされてます。

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

int main(){
    vector<int> v{23, 42, 33, 32, 23, 21, 74, 67, 70, 63};
    
    cout << "ソート前: ";
    for(int elm : v) {
        cout << elm << " ";
    }
    cout << endl;

    // 各値に-1をかける
    for(int &elm : v) {
        elm *= -1;
    }
    
    sort(v.begin(), v.end());

    // 各値に-1をかけて値を復元
    for(int &elm : v) {
        elm *= -1;
    }
    
    cout << "ソート後: ";
    for(int elm : v) {
        // 降順で出力される
        cout << elm << " ";
    }
    cout << endl;
    
    return 0;
}

ソート前: 23 42 33 32 23 21 74 67 70 63 
ソート後: 74 70 67 63 42 33 32 23 23 21 

便利な場面

pairをソートするときなどに応用させると便利です。例えば「firstの昇順→secondの降順」でソートしたい場合、secondの値に-1をかけてソートします。こうすることで比較関数を作ることなく想定していたソートが実現できます。

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

int main(){
    vector<pair<int, int>> v{{6, 79}, {53, 15}, {59, 13}, {6, 39}, {38, 67}, {20, 96}, {38, 33}, {53, 98}, {20, 4}, {59, 11}};

    cout << "ソート前: ";
    for(pair<int, int> elm : v) {
        cout << "{" << elm.first << ", " << elm.second << "} ";
    }
    cout << endl;

    // secondの各値に-1をかける
    for(pair<int, int> &elm : v) {
        elm.second *= -1;
    }

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

    // secondの各値に-1をかけて値を復元
    for(pair<int, int> &elm : v) {
        elm.second *= -1;
    }

    cout << "ソート後: ";
    for(pair<int, int> elm : v) {
        // firstの昇順→secondの降順で出力
        cout << "{" << elm.first << ", " << elm.second << "} ";
    }
    cout << endl;
    
    return 0;
}

ソート前: {6, 79} {53, 15} {59, 13} {6, 39} {38, 67} {20, 96} {38, 33} {53, 98} {20, 4} {59, 11} 
ソート後: {6, 79} {6, 39} {20, 96} {20, 4} {38, 67} {38, 33} {53, 98} {53, 15} {59, 13} {59, 11} 

これと似たような方法で降順ソートをしていたABCの解説が確かあって、私もそれで知ったのですが、どの問題だったか忘れてしまいました。。。

補足

競プロとしてのTips・テクニックです。他の場面で使うときは自己責任でお願いします。

1. 配列に入る値は$-10^9$以上、$10^9$以下を想定しています。 ↩