概要

本稿では、競技プログラミングやコーディングテストで頻出する「ソート」を中心とした 4 問の解法を紹介する。各問とも標準的なアルゴリズムを用いることで簡潔に解けるため、実装テクニックを押さえておくと非常に有利である。

問題 1：単純な昇順ソート

問題文

整数列が与えられる。昇順に並べ替えて出力せよ。

解法

要素数が 10⁵ 程度であれば、単純な挿入ソートでも間に合うが、より高速にするなら std::sort を用いるのが無難である。以下は挿入ソートを自前実装した例。

#include <iostream>
using namespace std;

const int MAX_N = 1e5;
long long seq[MAX_N];

void insertionSort(long long a[], int n) {
    for (int i = 1; i < n; ++i) {
        long long key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            --j;
        }
        a[j + 1] = key;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; ++i) cin >> seq[i];

    insertionSort(seq, n);

    for (int i = 0; i < n; ++i) {
        if (i) cout << ' ';
        cout << seq[i];
    }
    return 0;
}

問題 2：上位 m 件を降順で出力

問題文

n 人の所持金が与えられる。金額の大きい順に m 人分だけ出力せよ。

解法

全体をソートして末尾 m 件を逆順に取り出してもよいが、m ≪ n のときは「部分ソート」が効率的である。C++ なら std::nth_element を使うことで O(n) 時間で済ませられる。以下は簡易的な選択ソートで上位 m 件を求める実装。

#include <cstdio>
using namespace std;

const int MAX_N = 1e6;
int asset[MAX_N];

int main() {
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) return 0;

    for (int i = 0; i < n; ++i) scanf("%d", &asset[i]);

    // 簡易選択ソートで上位 m 件を決定
    for (int i = 0; i < m; ++i) {
        int maxIdx = i;
        for (int j = i + 1; j < n; ++j) {
            if (asset[j] > asset[maxIdx]) maxIdx = j;
        }
        if (maxIdx != i) {
            int tmp = asset[i];
            asset[i] = asset[maxIdx];
            asset[maxIdx] = tmp;
        }
    }

    for (int i = 0; i < m; ++i) {
        if (i) putchar(' ');
        printf("%d", asset[i]);
    }
    return 0;
}

問題 3：複数指標による国別ランキング

問題文

各国の金・銀・銅メダル数が与えられる。以下 4 種のルールで順位付けし、指定された国にとって最も良い順位を採用した際の「順位」と「採用ルール番号」を出力せよ。

1. 金メダル数の降順
2. 銀メダル数の降順
3. 金メダル ÷ 人口 の降順
4. 銀メダル ÷ 人口 の降順

解法

4 種のソートキーを事前に計算し、各ルールごとに国番号をソートする。同一値は同順位として扱う。最後に、指定国にとって最も順位が高い（数値が小さい）ルールを選択する。

#include <cstdio>
#include <algorithm>
using namespace std;

struct Country {
    double key[4];   // 各ルールでのスコア
    int    rank[4];  // 各ルールでの順位
};

const int MAX_N = 250;
Country countries[MAX_N];
int idx[MAX_N];

bool cmp(int a, int b, int rule) {
    return countries[a].key[rule] > countries[b].key[rule];
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 0; i < n; ++i) {
        double g, s, pop;
        scanf("%lf %lf %lf", &g, &s, &pop);
        countries[i].key[0] = g;
        countries[i].key[1] = s;
        countries[i].key[2] = g / pop;
        countries[i].key[3] = s / pop;
    }

    // 各ルールでソートし順位を記録
    for (int rule = 0; rule < 4; ++rule) {
        for (int i = 0; i < n; ++i) idx[i] = i;
        sort(idx, idx + n, [&](int a, int b){ return cmp(a, b, rule); });

        for (int pos = 0; pos < n; ++pos) {
            if (pos > 0 &&
                countries[idx[pos]].key[rule] == countries[idx[pos-1]].key[rule]) {
                countries[idx[pos]].rank[rule] = countries[idx[pos-1]].rank[rule];
            } else {
                countries[idx[pos]].rank[rule] = pos + 1;
            }
        }
    }

    for (int i = 0; i < m; ++i) {
        int q;
        scanf("%d", &q);
        int bestRule = 0;
        int bestRank = countries[q].rank[0];
        for (int rule = 1; rule < 4; ++rule) {
            if (countries[q].rank[rule] < bestRank) {
                bestRank = countries[q].rank[rule];
                bestRule = rule;
            }
        }
        if (i) putchar(' ');
        printf("%d:%d", bestRank, bestRule + 1);
    }
    return 0;
}

問題 4：K 回のバブルソート後の配列

問題文

長さ n の配列に対してバブルソートの交換処理を k 回だけ行った結果を出力せよ。

解法

バブルソートの特徴を活かし、各パスで末尾に最大値が沈む性質を利用。k 回目のパスまで実行したら即座に出力して終了すれば十分である。

#include <cstdio>
using namespace std;

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    int arr[n];
    for (int i = 0; i < n; ++i) scanf("%d", &arr[i]);

    for (int pass = 0; pass < k; ++pass) {
        for (int j = 0; j < n - pass - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        if (i) putchar(' ');
        printf("%d", arr[i]);
    }
    return 0;
}

以上、4 パターンのソート問題と実装例を示した。アルゴリズムを正しく理解し、言語標準ライブラリを活用することで、短時間で確実に解答できるだろう。