各種アルゴリズム

標準ライブラリのアルゴリズムの契約がタスクに適合する場合は、それらを使用してください。実装が対象プラットフォーム向けに最適化されているためです。

左側で最も近い小さい要素 #

スタック内の値を昇順に維持します。各インデックスは 1 回ずつ push と pop されるため、時間計算量は \(O(n)\)、空間計算量は \(O(n)\) です。

cpp

#include <cstddef>
#include <vector>

std::vector<int> nearest_left_smaller(const std::vector<int>& values) {
    std::vector<int> result(values.size(), -1);
    std::vector<std::size_t> stack;
    stack.reserve(values.size());

    for (std::size_t index = 0; index < values.size(); ++index) {
        while (!stack.empty() && values[stack.back()] >= values[index]) {
            stack.pop_back();
        }
        if (!stack.empty()) {
            result[index] = static_cast<int>(stack.back());
        }
        stack.push_back(index);
    }
    return result;
}

同じ値を持つ先行要素を有効とする場合は、>= の代わりに > を使用します。走査方向または比較方法を反転すると、次に大きい要素、株価スパン、ヒストグラム、気温クエリーの各バリエーションを実現できます。

素集合データ構造 #

サイズによる併合と経路半減により、find と unite の償却計算量は \(O(\alpha(n))\) になります。負のエントリーには、ルートが属する連結成分のサイズを格納します。

cpp

#include <utility>
#include <vector>

class DisjointSet {
public:
    explicit DisjointSet(int count) : parent_or_size_(count, -1) {}

    int find(int value) {
        while (parent_or_size_[value] >= 0) {
            const int parent = parent_or_size_[value];
            if (parent_or_size_[parent] >= 0) {
                parent_or_size_[value] = parent_or_size_[parent];
            }
            value = parent;
        }
        return value;
    }

    bool unite(int left, int right) {
        left = find(left);
        right = find(right);
        if (left == right) {
            return false;
        }
        if (parent_or_size_[left] > parent_or_size_[right]) {
            std::swap(left, right);
        }
        parent_or_size_[left] += parent_or_size_[right];
        parent_or_size_[right] = left;
        return true;
    }

private:
    std::vector<int> parent_or_size_;
};

両方の値がすでに同じ連結成分に属している場合、unite は false を返します。値は [0, count) の範囲内でなければなりません。

二分ヒープとヒープソート #

ヒープ構築の計算量は \(O(n)\) で、各 push または pop の計算量は \(O(\log n)\) です。

cpp

#include <algorithm>
#include <vector>

void heapsort(std::vector<int>& values) {
    std::make_heap(values.begin(), values.end());
    std::sort_heap(values.begin(), values.end());
}

std::sort_heap はインプレースで昇順に並べ替えます。ヒープソートの最悪時間計算量は \(O(n \log n)\)、補助記憶域は \(O(1)\) ですが、汎用的なソートには std::sort の方が適しています。

マージソートと転倒数の計算 #

同じ値の要素について入力時の順序を維持する必要がある場合は、std::stable_sort を使用します。マージソートの時間計算量は \(O(n \log n)\)、補助記憶域は \(O(n)\) です。

cpp

#include <algorithm>
#include <vector>

template <class T, class Compare>
void stable_sort_records(std::vector<T>& values, Compare compare) {
    std::stable_sort(values.begin(), values.end(), compare);
}

転倒数を数えるには、2 つのソート済み範囲をマージし、右側の要素を出力するたびに、未マージの左側要素の数を加算します。このアルゴリズムの計算量も \(O(n \log n)\) です。

素数ふるい #

オイラーのふるいは、すべての合成数について最小素因数を記録します。各合成数に 1 回だけ印を付けるため、時間計算量は \(O(n)\)、メモリー使用量は \(O(n)\) です。

cpp

#include <vector>

std::vector<int> least_prime_factors(int limit) {
    std::vector<int> least_prime(limit + 1);
    std::vector<int> primes;

    for (int value = 2; value <= limit; ++value) {
        if (least_prime[value] == 0) {
            least_prime[value] = value;
            primes.push_back(value);
        }
        for (int prime : primes) {
            if (prime > limit / value) {
                break;
            }
            least_prime[prime * value] = prime;
            if (prime == least_prime[value]) {
                break;
            }
        }
    }
    return least_prime;
}

除算を使ったガードにより、オーバーフローを防止します。真偽値の素数判定表にはエラトステネスのふるいを使用し、範囲全体をメモリーに格納できない場合は区間ふるいを使用します。

クイックセレクトとクイックソート #

イントロスペクティブな標準ライブラリアルゴリズムを使用してください。クイックソートの二次時間となる最悪ケースを回避し、範囲全体をソートせずに選択できるためです。

cpp

#include <algorithm>
#include <cstddef>
#include <vector>

void sort_values(std::vector<int>& values) {
    std::sort(values.begin(), values.end());
}

int select_nth(std::vector<int>& values, std::size_t rank) {
    std::nth_element(values.begin(), values.begin() + rank, values.end());
    return values[rank];
}

std::sort の比較回数は \(O(n \log n)\) です。std::nth_element の平均計算量は \(O(n)\) です。rank は values.size() 未満でなければならず、結果として得られるどちらの区間もソート済みではありません。