More than 5 years have passed since last update.

競技プログラミングの基本！全探索とSTL

Last updated at 2019-10-05Posted at 2019-10-05

競技プログラミングの基本！全探索とSTL

この記事は複数の例題を通して全探索とSTLになれることを目的としています．STLを使うことで問題をすっきり解くことができたり、考察の見通しが良くなったりと、非常に有用です．特に400点以上になるとデータ構造による高速化が必要となる問題が多くなるので緑以上を目指す方は必ず押さえておきましょう！
解答例は載せますが、解説は特につけていません（気が向いたらつけるかも？）
自力で実装するのが厳しい場合はコードを読んでSTLの使い方を学んでくれるといいなと思っています

全探索

全てのアルゴリズムの基本

アルゴリズムは全探索と貪欲法に大きく分けることができて，全探索は必ず答えを出すことができる．貪欲法は答えを出せるかわからないので証明が必要．

今回はA~B問題レベルの全探索をやってみよう．

普通に解いてもいいけど全探索の方が楽

STLのコンテナクラス

vector

可変長配列、push_backが便利

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n = 100;
    vector<int> v(n, 0); //サイズn、全要素を0で初期化
    for (int i = 0; i < 100; i++)
    {
        v[i] = i;
    }
    v.push_back(10);                                //末尾に10を挿入
    cout << v.size() << endl;                       //要素数
    reverse(v.begin(), v.end());                    //逆順
    sort(v.begin(), v.end(), greater<int>());       // 降順ソート
    sort(v.begin(), v.end());                       //　昇順ソート
    auto low = lower_bound(v.begin(), v.end(), 20); //二分探索 値以上の最小値を探索
    cout << *low << endl;
    auto up = upper_bound(v.begin(), v.end(), 20); //二分探索　値より大きい最小値を探索
    cout << *up << endl;
}

set

集合を管理する．中の実装は二分探索木

挿入，探索，削除がすべてO(log N)

unordered_setはO(１)だが，内部がソート済みにならないので嬉しくない

multisetは重複を許可する

#include <bits/stdc++.h>
using namespace std;
int main()
{
    set<int> s;
    s.insert(10);             //挿入
    s.erase(10);              //削除
    cout << s.size() << endl; //集合のサイズ
    for (int i = 0; i < 100; i++)
    {
        s.insert(i);
    }
    if (s.find(10) != s.end()) //値の探索　見つからないなら末尾を返す　
        cout << *s.find(10) << endl;
    auto low = s.lower_bound(30); //値の探索　引数以上の値の最小値へのポインタを返す
    cout << *low << endl;
    auto up = s.upper_bound(30); //値の探索　引数より大きい値の最小値へのポインタを返す
    cout << *up << endl;
    for (auto it : s) //拡張for文　内容を前から走査
    {
        cout << it << ' ';
    }
}

map

辞書、中はpairの二分探索木、アクセスはO(log N)

pairがsetで管理されていると思うと良い

unordered_mapはハッシュで管理される

#include <bits/stdc++.h>
using namespace std;
int main()
{
    map<string, int> m; //キーがstring 値がint
    m["ghi"] = 3;       //値の挿入
    m["def"] = 2;
    m["abc"] = 1;
    cout << m["def"] << endl;
    for (auto it : m) //拡張for、中身はペア、キーの昇順
    {
        cout << it.first << ' ' << it.second << endl;
    }
}

priority_queue

ヒープ，集合の最小値 or 最大値を得たいときに有効

挿入O(log N)，最小値(最大値)の参照O(１)，最小値(最大値)の削除O(log N)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    priority_queue<int> que;                             //最大値から出るヒープ
    priority_queue<int, vector<int>, greater<int>> que2; //最小値から出るヒープ
    vector<int> v = {10, 5, 1, 7, 21, 13};
    for (auto it : v)
    {
        que.push(it); //挿入
        que2.push(it);
    }
    while (!que.empty()) //空かどうか判定
    {
        int x = que.top(); //参照
        que.pop(); //　削除
        cout << x << ' ';
    }
    cout << endl;
    while (!que2.empty())
    {
        int x = que2.top();
        que2.pop();
        cout << x << ' ';
    }
    cout << endl;
}

pair

値のペア，ペアで値を管理したい時がある

３つ以上はタプルを使うか，自分で構造体を作る方が便利

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int main(){
    P p = P(1,2);
    cout << p.first << ' ' << p.second << endl;
}