Go to Qiita Advent Calendar 2024 Top
LoginSignup
1107
1070

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@e869120(E869120)

厳選！C++ アルゴリズム実装に使える 25 の STL 機能【前編】

Last updated at Posted at 2020-01-26

0. あいさつ

こんにちは、高校 2 年生のE869120です。
今回は、競技プログラミング (競プロ) やアルゴリズムの学習・実装において役立ちそうな C++ の標準ライブラリ（STL）と、その応用例について解説していきたいと思います。

【シリーズ】

1. はじめに

皆さん、C++ というプログラミング言語を使ったことがありますか？

C++ は アルゴリズム の学習・実装の世界では最も利用者数が多い言語の一つであり、「アルゴリズムとデータ構造」などたくさんのアルゴリズム解説本において C++ のサンプルコードが書かれています。また、競技プログラミング (競プロ) において C++ は大人気であり、競技プログラマーの約半数が C++ を利用しています。1

プログラミング言語 提出ソースコード数 割合（％）
C++ / C++14 22,230 51.7%
Python3 10,482 24.4%
PyPy3 3,125 7.3%
Java 1,931 4.5%
その他 5,199 12.1%
合計 42,967 100.0%
(AtCoder Beginner Contest 152 で提出されたソースコードの分類)

それほど C++ が、競プロやアルゴリズムの学習に人気であるのには、以下のような理由があるのです。

  • 計算速度が 1 秒あたり $10^{8} ～ 10^{9}$ 回程度と、他のプログラミング言語に比べ高速だから。
  • 基礎的文法の習得がそれほど難しくないから。

しかし、C++ の利点はこれだけではありません。元々用意されている標準ライブラリがあるのです。一方、標準ライブラリは C++ を学ぶ大きな障壁となるものの一つです。C++ を学ぶ上で標準ライブラリが上手く使えず挫折したという人も多いと思います。そこで本記事では、

競技プログラミングやアルゴリズムの実装に使える 25 個の C++ 標準ライブラリと、それらの各種アルゴリズム実装への応用例

を解説したいと思います！！！！！

本記事を読んだら何ができるのか？

前編(本記事) と後編を読み、この記事でリストアップされた 25 個の C++ 標準ライブラリをすべて使えるようになれば、以下の 3 つのことができるようになると思います。

  • 多くのアルゴリズムを楽に実装することができる。実際に、標準ライブラリを使うのと使わないのでは、大幅に実装コード長が異なる。
  • アルゴリズム解説本・競プロの問題解説に書かれてあるほとんどのソースコードを読むことができる。実際に、「アルゴリズムとデータ構造」という本に書かれたサンプルコードの 90% 程度2は 25 個の標準ライブラリでカバーされている。
  • 競技プログラミングにおいて、短く簡潔なコードを書くことができる。

目次

前編

章 タイトル 備考
1. はじめに
2. C++ の標準ライブラリとは？ 基本から説明していきます！
3. 今回紹介する 25 個の標準ライブラリ 本記事のメインコンテンツです！
4. 皆さんの疑問　「標準ライブラリ、結局どんな場面で使えるのか？」

後編

章 タイトル 備考
5. 皆さんの疑問　「標準ライブラリ、結局どんな場面で使うのか？」に対する回答 11 例 本記事の最も面白いところです。C++ の STL がどこで使えるのか、11 例紹介します！
6. おわりに
7. 参考文献

2. C++ の標準ライブラリとは？

「標準ライブラリ」は、以下のようなものです。

通例的に言語の各実装に備えられているライブラリ。

C++ というプログラミング言語には、様々な標準ライブラリ (STL) が用意されています。例えば、

などの便利な計算処理ができるということは、知っている人も多いと思います。

しかし、できることはそれだけではありません。**C++ には、便利機能から各種アルゴリズムまで非常に多くの標準ライブラリが備え付けられており、他のプログラミング言語に比べてもその種類の数と幅の広さはとても多いのです。**競技プログラミングやアルゴリズム実装において、C++ 標準ライブラリは運命そのものなのです。

本記事の前提

本記事では、C++11 以降を使うものとします。

標準ライブラリを使う方法

標準ライブラリはどのような環境でも利用することができ、付属の環境をインストールする必要が一切ありません。もちろん、AtCoder や ideone.com でも使うことができます。ただし、使うためには、ソースコードの最初に以下のような文を加える必要があります。

gcc の場合

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

その他の環境の場合（Visual Studio 2019 を含む）

#include <iostream>
#include <string>
#include <algorithm> 
// などの必要なインクルードファイルすべて（3章の各標準ライブラリの説明でそれぞれ書いています）
using namespace std;

なお、bits/stdc++.h は、gcc で使えるとても恐ろしいインクルードファイルであり、この一文ですべての標準ライブラリを使うことができます。3

注記（中上級者向け）

本記事の内容から多少逸れますが、サンプルコード 2 行目の using namespace std; とは何なのか説明します。

これを付けなければ、C++ でサポートされている各標準ライブラリに std:: を付ける必要があります。（cin の場合 std::cin、cout の場合 std::cout など。）using namespace std; の一文を書くことによって、std:: を省略することができます。（ @keymoon さんからコメントを頂きました。）

また、一部の機能は何もインクルードすることなく使えます、と書かれておりますが、iostream などでは他の様々なファイルをインクルードしているからです。例えば、iostream をインクルードすれば、同時に utility もインクルードされたりします。 ( @TumoiYorozu さんからコメントを頂きました。)

3. 今回紹介する 25 個の標準ライブラリ

本記事では、以下の 25 個の標準ライブラリを解説します。4

導入編
理解するのが簡単なものが中心です。
多くの人は知っていると思います。

節 標準ライブラリ
3-1. 絶対値 abs
3-2. 三角関数 sin/cos/tan
3-3. 文字列 string

初級編
基本的なアルゴリズムの実装に必要なライブラリです。（AtCoder の 100-300 点問題レベルでもよく使われます）
アルゴリズム以外の場面でも使われることが多いかもしれません。

節 標準ライブラリ
3-4. 最大値・最小値 min/max
3-5. 値の交換 swap
3-6. 最大公約数 __gcd
3-7. 乱数 rand
3-8. 時間計測 clock
3-9. 配列を逆順に並び替え reverse
3-10. ソート sort

中級編第一部
基本的なアルゴリズムの実装に必要なライブラリです。（AtCoder の 200-400 点問題レベルでもよく使われます）

節 標準ライブラリ
3-11. vector
3-12. stack
3-13. queue
3-14. priority_queue
3-15. map
3-16. lower_bound
3-17. set
3-18. pair
3-19. tuple

中級編第二部
第一部ほどではないですが使われるので、知っていて損はないでしょう。
AtCoder 水色～黄色の上級者でも知らないものがあるかもしれません。

節 標準ライブラリ
3-20. assert
3-21. count
3-22. find
3-23. next_permutation
3-24. __builtin_popcount
3-25. bitset

なお、競技プログラミングやアルゴリズム実装に使えるものしか本記事に書かれておりませんので、ifstream や limits などといった、アルゴリズム実装とあまり関係ない標準ライブラリは書かれておりません。すべての C++ 標準ライブラリを知りたい方は、cppreference.com の記事 をご覧ください。

3-1. 絶対値 abs

x の絶対値を返す関数です。

概要

abs(x) = (x の絶対値) となります。例えば、

  • abs(-16) = 16
  • abs(8) = 8

となります。また、abs 関数は int 型などの整数型だけでなく、double 型などの浮動小数点型にも対応しています。cmath をインクルードすることで使えます。

サンプルコード

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    // 例 1: 2 つの小数 a と b を入力し、a-b の絶対値を小数で出力します。
    double a, b;
    cin >> a >> b;
    printf("%.12lf\n", abs(a - b));
    return 0;
}

3-2. 三角関数 sin/cos/tan

三角関数です。高校数学でも習ったかもしれませんが、知らない人は以下の記事をお読みください。

概要

C++ で使える三角関数の代表的なものは、以下の表のようになります。

関数 説明
sin(x) sin(x) の値を double 型で返します。例えば、sin(π/6) = 0.5 です。
cos(x) cos(x) の値を double 型で返します。例えば、cos(π/6) = 0.866025... です。
tan(x) tan(x) の値を double 型で返します。例えば、tan(π/6) = 0.577350... です。

なお、C++ では角度 $x$ は度数法ではなく弧度法を用いることにご注意ください。cmath をインクルードすることで使えます。

サンプルコード

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    // 例 1: 悪い例です。三角関数は弧度法を使いましょう（この場合 -0.988031... と出力されます）
    printf("%.12lf\n", sin(30));
    
    // 例 2: 三角関数の利用例。x を角度で入力し、sin(x),cos(x),tan(x) の値を出力します。
    double pi = 3.141592653589793238;
    double x;
    cin >> x;
    printf("%.12lf\n", sin(x / 180.0 * pi));
    printf("%.12lf\n", cos(x / 180.0 * pi));
    printf("%.12lf\n", tan(x / 180.0 * pi));
    return 0;
}

3-3. 文字列 string

文字列を扱う型です。int も double も型ですが、string も型の一種です。

概要

ここでは、S, T を string 型の変数、c を char 型の変数とします。以下のような処理ができます。

プログラム 説明
string S; string 型の変数 S を定義します。
cin >> S; 文字列 S を入力します。
cout << S; 文字列 S を出力します。
S[i] S の i 文字目です。char 型配列と同じようなものだと思ってください。例えば、S[i] = 'z' という処理を行うと i 文字目が 'z' に変わります。
S += T; 文字列 S に文字列 T を連結します。例えば、S = "a", T = "bc" の場合、S が "abc" に変わります。S = S + T も同様です。
S += c; 文字列 S に char 型の文字 c を連結します。例えば、S = "qiit", c = 'a' の場合、S が "qiita" に変わります。S = S + c も同様です。
S.size() 文字列 S の長さを整数型で返す関数です。
S.substr(l) 文字列 S の l 文字目から最後の文字までの部分文字列を返す関数です。
S.substr(l, r) 文字列 S の l 文字目から l+r-1 文字目までの部分文字列を返す関数です。

なお、文字列は 0 文字目から始まることにご注意ください。文字列の大小比較は辞書式順序で決められます。string をインクルードすることで使えます。

サンプルコード

#include <iostream>
#include <string>
using namespace std;

int main() {
    // 例 1: 入力した 2 つの文字列を連結して、最初の 10 文字を出力します。
    string a, b;
    cin >> a >> b;
    string c = a + b;
    if (c.size() <= 10) cout << c << endl;
    else cout << c.substr(0, 10) << endl;

    // 例 2: 入力した文字列 s の偶数文字目を 'z' に変えて出力します。
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i += 2) s[i] = 'z';
    cout << s << endl;
    return 0;
}

3-4. 最小値・最大値 min/max

複数の値の、最小値・最大値を返す関数です。

概要

C++ で使える、最小値・最大値を取る関数は、以下の表のようになります。ここでは、c を適当な型の配列とします。

プログラム 説明
min(a, b) 2 つの値 a, b のうち小さい方を返します。
max(a, b) 2 つの値 a, b のうち大きい方を返します。
min({a1, a2, ..., an}) {a1, a2, ..., an} の中で最小のものを返します。
max({a1, a2, ..., an}) {a1, a2, ..., an} の中で最大のものを返します。
*min_element(c + l, c + r) {c[l], c[l+1], ..., c[r-1]} の中で最小のものを返します。
*max_element(c + l, c + r) {c[l], c[l+1], ..., c[r-1]} の中で最大のものを返します。

なお、min_element 関数と max_element 関数はイテレーターを返すため、最初に * を付ける必要があります。algorithm をインクルードすることで使えます。

サンプルコード

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

int main() {
    // 例 1: 103, 168, 103 の中で最も大きい値を出力する : 168 が出力される
    cout << max({103, 168, 103}) << endl;
    
    // 例 2: {c[1], c[2], ..., c[N]} の最小値を出力する方法 1 つ目
    int N, c[100009], minx = 2147483647;
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> c[i];
    for (int i = 1; i <= N; i++) minx = min(minx, c[i]);
    cout << minx << endl;

    // 例 3: {c[1], c[2], ..., c[N]} の最小値を出力する方法 2 つ目
    cout << *min_element(c + 1, c + N + 1) << endl;
    return 0;
}

3-5. 値の交換 swap

2 つの変数を交換する関数です。

概要

swap(a, b) で、変数 a と b の値を入れ替えることができます。例えば、a = 229, b = 108 の状態から swap(a, b) が呼び出されると、a = 108, b = 229 となります。追加のインクルードファイル呼び出しは必要ありません。

サンプルコード

バブルソートについて知らない人は、この記事をお読みください。

#include <iostream>
using namespace std;

int main() {
    // 例 1: 2 つの変数 a, b を入れ替え、出力する
    int a, b;
    cin >> a >> b;
    swap(a, b);
    cout << a << " " << b << endl;
    
    // 例 2: バブルソートによって、{c[1], c[2], ..., c[N]} を小さい順に並び替え、出力する
    int N, c[1009];
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> c[i];
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N - i; j++) {
            if (c[j] > c[j + 1]) swap(c[j], c[j + 1]);
        }
    }
    for (int i = 1; i <= N; i++) cout << c[i] << endl;
    return 0;
}

3-6. 最大公約数 __gcd

2 つの整数 a, b の最大公約数を返す関数です。
この関数は gcc で利用可能ですが、Visual Studio 2019 などでは使えません。

概要

__gcd(a, b) = (a と b の最大公約数) となります。例えば、

  • __gcd(8, 16) = 8
  • __gcd(234, 217) = 1

となります。計算量は $O(\log a)$ なので、とても高速です。algorithm をインクルードすることで使えます。

最小公倍数を返す標準ライブラリの関数はありませんが、a と b の最小公倍数は a / __gcd(a, b) * b で計算することができます。

この書き方は、a * b / __gcd(a, b) よりオーバーフローを起こしにくいです。

追記

@yumetodo さんによるコメント：C++17 以降では gcd/lcm が使えます。
ただし、AtCoder では C++14 までしか使えません。(yukicoder などでは使えます)

サンプルコード

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

int main() {
    // 例 1: 2 つの整数 a, b を入力し、a と b の最大公約数と最小公倍数を出力する
    int a, b;
    cin >> a >> b;
    cout << __gcd(a, b) << endl;
    cout << a / __gcd(a, b) * b << endl;
    return 0;
}

3-7. 乱数 rand

乱数を生成する関数です。

概要

基本的に、以下の 2 つをセットで覚えておくと良いと思います。

プログラム 説明
rand() $0$ 以上 $2^{31}-1$ 以下のランダムな整数を返す関数です。
srand((unsigned)time(NULL)); おまじないです。main 関数の冒頭にこれを付けると、実行ごとに乱数生成結果が変わります。

gcc の場合 $2^{31}-1$ までの乱数が生成されますが、Visual Studio 2019 の場合 $2^{15}-1$ までの乱数しか生成されないのでご注意ください。ctime をインクルードすることで使えます。
なお、乱数の質が完全とはいえないので、より良質な乱数を生成したい場合は random をインクルードして、メルセンヌ・ツイスタ (C++ では std::mt19937) などを使いましょう。

サンプルコード

#include <iostream>
#include <ctime>
using namespace std;

int main() {
    srand((unsigned)time(NULL));
    
    // 例 1: 1 以上 6 以下のランダムな整数を出力する
    cout << rand() % 6 + 1 << endl;

    // 例 2: 90% の確率で "Yay!"、10% の確率で ":(" と出力する
    if (rand() % 10 <= 8) cout << "Yay!" << endl;
    else cout << ":(" << endl;
    return 0;
}

3-8. 時間計測 clock

時間を計測する関数です。

概要

基本的に、以下の 2 つをセットで覚えておくと良いと思います。

プログラム 説明
clock() プログラム実行開始から何単位時間経過したかを整数で返す関数です。
CLOCKS_PER_SEC 定数です。環境によって1 秒が何単位時間か異なるので、秒数を知りたいときに使えます。

つまり、実行開始からの秒数は clock()/CLOCKS_PER_SEC で表されます。ちなみに、CLOCKS_PER_SEC の値は

  • gcc の場合 1000000
  • Visual Studio 2019 の場合 1000

となります。ctime をインクルードすると使えます。

サンプルコード

#include <iostream>
#include <ctime>
using namespace std;

int main() {
    // 例 1: 実行にかかる時間を計測する
    int ti = clock();
    for (int i = 1; i <= 100000; i++) cout << i << endl;
    printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
    return 0;
}

3-9. 配列を逆順に並び替え reverse

配列のある区間を逆順に並び替える関数です。

概要

逆順に並び替える関数は、基本的に以下の表のようになります。ここでは、a を適当な型の配列とします。

プログラム 説明
reverse(a, a + N) a[0], a[1], ..., a[N-1] を逆順に並び替えます。
例えば、a = {2, 1, 4, 3, ...} のときに reverse(a, a + 3) という操作を行うと、a = {4, 1, 2, 3, ...} となります。
reverse(a + l, a + r) a[l], a[l+1], ..., a[r-1] を逆順に並び替えます。

計算量は $O(N)$ です。文字列 str を逆順にしたい場合は、reverse(str.begin(), str.end()) のように書いてください。 algorithm をインクルードすることで使えます。

サンプルコード

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

int main() {
    // 例 1: 配列 a の 2～6 番目の要素を逆順にします。{8, 3, 2, 6, 4, 1, 7, 5} に変化します。
    int a[8] = {8, 3, 7, 1, 4, 6, 2, 5};
    reverse(a + 2, a + 7);
    for (int i = 0; i < 8; i++) cout << a[i] << endl;
    
    // 例 2: {b[0], b[1], ..., b[N-1]} を入力し、逆順にしたうえで出力します。
    int N, b[1009];
    cin >> N;
    for (int i = 0; i < N; i++) cin >> b[i];
    reverse(b, b + N);
    for (int i = 0; i < N; i++) cout << b[i] << endl;
    return 0;
}

3-10. ソート sort

配列のある区間を小さい順などに並び替える関数です。

概要

以下の 3 つの書き方を覚えておくと、大体の競プロの問題において使えます。

プログラム 説明
sort(a, a + N); a[0], a[1], ..., a[N-1] を小さい順に並び替えます。
sort(a + l, a + r); a[l], a[l+1], ..., a[r-1] を小さい順に並び替えます。
sort(a, a + N, greater< int >()); a[0], a[1], ..., a[N-1] を大きい順に並び替えます。
int 型の要素をソートする場合は greater< int >() を付けます。
double 型の要素をソートする場合は greater< double >() を付けます。

計算量は $O(N \log N)$ です。なお、string 型のソートでは、辞書式順序で早い方が小さいとみなされます。algorithm をインクルードすることで使えます。greater< int >() を使う場合は functional もインクルードする必要があります。

サンプルコード

#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
    // 例 1: 配列 a の 1～4 番目を大きい順に並び替えます。{8, 7, 4, 3, 1, 6, 2, 5} に変化。
    int a[8] = {8, 3, 7, 1, 4, 6, 2, 5};
    sort(a + 1, a + 5, greater<int>());
    for (int i = 0; i < 8; i++) cout << a[i] << endl;
    
    // 例 2: {b[0], b[1], ..., b[N-1]} を入力し、小さい順に並び替えて出力します。
    int N, b[100009];
    cin >> N;
    for (int i = 0; i < N; i++) cin >> b[i];
    sort(b, b + N);
    for (int i = 0; i < N; i++) cout << b[i] << endl;
    return 0;
}

3-11. vector

vector は動的な配列を表す型です。

概要

ここでは、a を vector 型の変数、x を適当な変数または値とします。vector というデータ構造では、以下の処理ができます。

プログラム 説明
vector< int > a; vector 型の変数 a を定義します。
vector< int > の場合、vector には int 型の要素を入れます。
vector< double > の場合、vector の要素には double 型の要素を入れます。
a.push_back(x); a の末尾に x を追加します。
例えば a = {3, 1, 4} の状態で a.push_back(1); という処理が行われると、a = {3, 1, 4, 1} となります。
a.pop_back(); a の末尾の要素が取り除かれます。
例えば a = {3, 1, 4} の状態で a.pop_back(); という処理が行われると、 a = {3, 1} となります。
a[i] a の先頭から数えて i 番目の要素にアクセスできます。基本的には配列と同じで、演算や書き換えもできます。0 番目から始まることに注意してください。
a.size() a に現在いくつ要素が入っているか、整数型で返します。

計算量は、push_back、pop_back 両方 $O(1)$ と高速です。また、メモリ使用量も効率的で、入っている要素全部のバイト数合計と同じオーダーとなります。一つ注意点があって、vector で sort をする場合、sort(a, a + N) ではなく、

  • 最初から最後までソートする場合：sort(a.begin(), a.end())
  • l 番目から r 番目までソートする場合：sort(a.begin() + l, a.begin() + r)

のように書く必要があります。reverse の場合も同様です。vector をインクルードすることで使えます。

サンプルコード

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 例 1: a に色々な操作を行う（x1 = 105, x2 = 2, x3 = 146 となります）
    vector<int> a; // その時点で a は空
    a.push_back(121); // その時点で a = {121}
    a.push_back(105); // その時点で a = {121, 105}
    a.push_back(193); // その時点で a = {121, 105, 193}
    int x1 = a[1];
    a.pop_back(); // その時点で a = {121, 105}
    int x2 = a.size();
    a.push_back(146); // その時点で a = {121, 105, 146}
    int x3 = a[2];
    cout << x1 << " " << x2 << " " << x3 << endl;
    return 0;
}

3-12. stack

スタックというデータ構造を管理できる型です。もの（値）を積み上げたり、一番上のものを取ったりできるデータ構造です。イメージをつかむために、下の GIF 画像を見ると良いと思います。
draft1.gif

概要

ここでは、a を stack 型の変数、x を適当な型の変数または値とします。stack というデータ構造では、以下の処理ができます。

プログラム 説明
stack< int > a; stack 型の変数 a を定義します。
stack< int > の場合、スタックに int 型の要素を積みます。
stack< double > の場合、スタックに double 型の要素を積みます。
a.push(x) スタック a の一番上に要素 x を積みます。
a.pop() スタック a の一番上の要素を取り除きます。
a.top() スタック a の一番上の要素を返す関数です。
例えば、下から順に {3, 1, 4} と積み上げられている場合、a.top() の値は 4 です。
a.size() スタック a の要素数を整数で返す関数です。
a.empty() スタック a の要素数が 0 である場合 true、1 以上である場合 false を返す関数です。

push、pop、top などの計算量はすべて $O(1)$ です。実質的には vector の下位互換ですが、アルゴリズムなどの参考書で stack が利用されることが多いので、本記事でも紹介しておきました。stack をインクルードすることで使えます。

サンプルコード

#include <iostream>
#include <stack>
using namespace std;

int main() {
    // 例 1: a に色々な操作を行う（x1 = 156, x2 = 202, x3 = 117, x4 = 3, x5 = 0 となります）
    stack<int> a;
    a.push(179); // その時点で下から順に {179}
    a.push(173); // その時点で下から順に {179, 173}
    a.push(156); // その時点で下から順に {179, 173, 156}
    int x1 = a.top();
    a.pop(); // その時点で下から順に {179, 173}
    a.push(117); // その時点で下から順に {179, 173, 117}
    a.push(202); // その時点で下から順に {179, 173, 117, 202}
    int x2 = a.top();
    a.pop(); // その時点で下から順に {179, 173, 117}
    int x3 = a.top();
    int x4 = a.size();
    int x5 = 0; if (a.empty()) x5 = 10000;

    cout << x1 << " " << x2 << " "<< x3 << " " << x4 << " " << x5 << endl;
    return 0;
}

3-13. queue

待ち行列のようなデータ構造を管理できる型です。イメージをつかむために、下の GIF 画像を見ると良いと思います。
draft2.gif

概要

ここでは、a を queue 型の変数、x を適当な型の変数または値とします。queue というデータ構造では、以下の処理ができます。

プログラム 説明
queue< int > a; queue 型の変数 a を定義します。
queue< int > の場合、キューに int 型の要素を入れます。
queue< double > の場合、キューに double 型の要素を積みます。
a.push(x) キュー a の最後尾に要素 x を入れます。
a.pop() キュー a の一番前の要素を取り除きます。
a.front() キュー a の一番前の要素を返す関数です。
例えば、前から順に a = {3, 1, 4} である場合、3 を返します。
a.size() キュー a の要素数を返す関数です。
a.empty() キュー a の要素数が 0 である場合 true、1 以上である場合 false を返す関数です。

push、pop、front などの計算量はすべて $O(1)$ です。詳しくは後編で述べますが、幅優先探索や最短経路問題などでこのデータ構造が利用できます。queue をインクルードすることで使えます。

サンプルコード

#include <iostream>
#include <queue>
using namespace std;

int main() {
    // 例 1: a に色々な操作を行う（x1 = 179, x2 = 173, x3 = 156, x4 = 3, x5 = 0 となります）
    queue<int> a;
    a.push(179); // その時点で前から順に {179}
    a.push(173); // その時点で前から順に {179, 173}
    a.push(156); // その時点で前から順に {179, 173, 156}
    int x1 = a.front();
    a.pop(); // その時点で前から順に {173, 156}
    a.push(117); // その時点で前から順に {173, 156, 117}
    a.push(202); // その時点で前から順に {173, 156, 117, 202}
    int x2 = a.front();
    a.pop(); // その時点で前から順に {156, 117, 202}
    int x3 = a.front();
    int x4 = a.size();
    int x5 = 0; if (a.empty()) x5 = 10000;

    cout << x1 << " " << x2 << " "<< x3 << " " << x4 << " " << x5 << endl;
    return 0;
}

3-14. priority_queue

優先度付きキューというデータ構造を管理できる型です。イメージをつかむために、下の GIF 画像を見ると良いと思います。
draft3.gif

概要

ここでは、a を priority_queue 型の変数、x を適当な型の変数または値とします。priority_queue というデータ構造では、以下の処理ができます。

プログラム 説明
a.push(x) 優先度付きキュー a に要素 x を追加します。
a.pop() a の中の最も小さい要素（設定によっては、最も大きい要素）を取り除きます。
a.top() a の中の最も小さい要素（設定によっては、最も大きい要素）の値を返す関数です。
a.size() a の要素数を返す関数です。
a.empty() a の要素数が 0 の場合 true、1 以上である場合 false を返す関数です。

$N$ を優先度付きキューに入っている要素数とするとき、push、pop、top の計算量は $O(\log N)$ です。queue、vector、functional をインクルードすることで使えます。

変数の定義

変数の定義方法がやや特殊なので、書いておきます。以下のように、最も小さい値を取り出したい場合は greater、最も大きい値を取り出したい場合は less を使います。

// int 型の要素を持ち、最も小さい値を取り出す形の priority_queue を定義する場合
priority_queue<int, vector<int>, greater<int>> Q1;

// double 型の要素を持ち、最も小さい値を取り出す形の priority_queue を定義する場合
priority_queue<double, vector<double>, greater<double>> Q2;

// int 型の要素を持ち、最も大きい値を取り出す形の priority_queue を定義する場合
priority_queue<int, vector<int>, less<int>> Q3;

サンプルコード

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

int main() {
    // 例 1: Q に色々な操作を行う（x1 = 116, x2 = 110, x3 = 122, x4 = 2 となります）
    priority_queue<int, vector<int>, greater<int>> Q;
    Q.push(116); // この時点で、小さい順に {116}
    Q.push(145); // この時点で、小さい順に {116, 145}
    Q.push(122); // この時点で、小さい順に {116, 122, 145}
    int x1 = Q.top();
    Q.push(110); // この時点で、小さい順に {110, 116, 122, 145}
    int x2 = Q.top();
    Q.pop(); // この時点で、小さい順に {116, 122, 145}
    Q.pop(); // この時点で、小さい順に {122, 145}
    int x3 = Q.top();
    int x4 = Q.size();
    
    cout << x1 << " " << x2 << " " << x3 << " " << x4 << endl;
    return 0;
}

3-15. map

どんな「番地」にも書き込める、無限配列のようなデータ構造です。

例えば、int A[100000] という配列を定義すれば、0 ～ 99999 番地までにしか書き込むことができません。一方で、map を使えば、配列の番地として int 型だけではなく、string 型や後述する pair 型まで使えます。イメージをつかむために、以下の画像を見ると良いと思います。
スライド1.JPG

概要

a を map 型の変数、x を適当な型の変数とします。map というデータ構造は、以下の処理ができます。

プログラム 説明
a[x] マップの x という番地にアクセスする感じだと思ってよいです。配列と同じように、代入・演算ができます。x は整数型でなくても、文字列型でも vector 型でも何でもありです。
a.clear() マップ a を初期化します。

なお、最初は値がすべて 0（文字列の場合は空文字列）で初期化されています。
$N$ を今まで map 型変数にアクセスした数とするとき、マップのある特定の番地へのアクセスにかかる計算量は $O(\log N)$ 程度です。map をインクルードすることで使えます。

変数の定義

変数の定義方法がやや特殊なので、書いておきます。基本的に、map< 番地の型, 記録する型 > となります。

// int 型の番地に int 型の変数を記録する場合（2^31 要素の int 型配列と同じような感じ）
map<int, int> M1;

// int 型の番地に string 型の変数を記録する場合（2^31 要素の string 型配列と同じような感じ）
map<int, string> M2;

// string 型の番地に double 型の変数を記録する場合
map<string, double> M3;

サンプルコード

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main() {
    map<string, int> Map;
    Map["qiita"] = 777;
    Map["algorithm"] = 1111;
    Map["competitive_programming"] = 1073741824;
    
    cout << Map["algorithm"] << endl; // 1111 と出力される
    cout << Map["tourist"] << endl; // まだ何も書き込まれていないので、0 と出力される
    return 0;
}

3-16. lower_bound

二分探索 をすることができる関数です。

概要

配列 a があったとして、a の l 番目から r-1 番目までの要素が小さい順にソートされていたとしましょう。

そのとき、lower_bound(a+l, a+r, x) - a というプログラムは、

  • a[l] から a[r-1] までの中で初めて x 以上となるようなインデックスを返します。
  • つまり、$l \leq i \leq r-1$ の中で、$x \leq a_i$ となるような最小の $i$ の値を返します。
  • 例えば、a = {2, 3, 4, 6, 9, ...} の場合、lower_bound(a, a + 5, 7) - a = 4 となります。

計算量は $O(\log \ N)$ です。algorithm をインクルードすることで使えます。

サンプルコード

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

int main() {
    // 例 1: a[i] < x となるような i が何個あるのかを O(log N) で計算する
    int N, a[100009];
    cin >> N;
    for (int i = 0; i < N; i++) cin >> a[i];
    sort(a, a + N);

    int x;
    cin >> x;
    cout << lower_bound(a, a + N, x) - a << endl;
    return 0;
}

3-17. set

集合を管理することができるデータ構造です。集合に要素を追加したり、削除したり、二分探索したりできます。このようなデータ構造には、set と multiset の 2 種類があります。

概要

set 型の変数 a と、適当な型の変数または値 x があったとして、以下の処理ができます。（ここでは、y は set 内の要素を指すイテレーターとします。）

プログラム 説明
a.insert(x) 集合 a に要素 x を追加する。但し、既に x が集合 a にある場合は追加しない。
（multiset の場合、既に要素が 1 個以上あっても追加する。）
a.erase(x) 集合 a から要素 x を削除する。（multiset の場合、要素 x をすべて削除する。）
a.erase(y) 集合 a からイテレーター y の要素を削除する。
（この場合、multiset の場合でも 1 個だけ消すことができる。）
a.lower_bound(x) 集合 a の中で x 以上である最小の要素を指すイテレーターを返す。
a.clear() 集合 a を空にする。

$N$ 個の要素を持つ set に対する操作の計算量は、大体の操作で $O(log \ N)$ です。（multiset も同様。）

なお、set 内では小さい順に要素が並んでいます。そのため、イテレーター itr に対し

  • itr++ とすると、set 内の一つ大きい要素を指すようになります
    • 例えば a = {2,3,4,6,8} で元々 (*itr) = 6 の場合、itr++ をすると itr は 8 を指すようになる
  • itr-- とすると set 内の一つ小さい要素を指すようになります
    • 例えば a = {2,3,4,6,8} で元々 (*itr) = 6 の場合、itr-- をすると itr は 4 を指すようになる

また、a.begin() は set 内の先頭のイテレーター、a.end() は set 内の末尾のイテレーターを指します。少し難しいので、もしわからなければこちらを読むと良いと思います。set をインクルードすることで使えます。

サンプルコード

#include <iostream>
#include <set>
using namespace std;

int main() {
    // 例 1: set に対して色々な操作を行う（1 個目は "End"、2 個目は "46" と出力される）
    set<int> Set;
    Set.insert(37); // その時点での Set の要素は {37}
    Set.insert(15); // その時点での Set の要素は {15, 37}
    Set.insert(37); // その時点での Set の要素は {15, 37}
    auto itr1 = Set.lower_bound(40);
    if (itr1 == Set.end()) cout << "End" << endl;
    else cout << (*itr1) << endl;
    Set.erase(37); // その時点での Set の要素は {15}
    Set.insert(46); // その時点での Set の要素は {15, 46}
    auto itr2 = Set.lower_bound(20);
    if (itr2 == Set.end()) cout << "End" << endl;
    else cout << (*itr2) << endl;

    // 例 2: a[1],a[2],...,a[N] を小さい順に出力する（同じ要素が複数ある場合 1 回だけ出力する）
    set<int> b; int N, a[100009];
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> a[i];
    for (int i = 1; i <= N; i++) b.insert(a[i]);
    auto itr = b.begin();
    while (itr != b.end()) {
        cout << (*itr) << endl;
        itr++;
    }
    return 0;
}

3-18. pair

pair は 2 つの異なる型を一つの変数で持つことができる「組」を表現できる型です。

概要

pair は 2 つの要素を持てる型です。a を pair 型の変数とするとき、

  • 1 つ目の要素は a1.first
  • 2 つ目の要素は a1.second

で表されます。また、1 つ目の要素の型を v1, 2 つ目の要素の型を v2 とするとき、pair< v1, v2 > a; という感じで変数を定義できます。例えば、両方 int 型にしたい場合は pair< int, int > a; という感じで変数を定義できます。

2 つの pair 型要素の大小比較は、以下のように決められます。

  • 1 つ目の要素が小さい方を小さいとみなす。
  • 1 つ目の要素が同じである場合、2 つ目の要素が小さい方を小さいとみなす。

なお、pair 型は追加のインクルードファイル無しで使えます。（本来は utility ファイル内の型ですが、実際にはインクルードしなくても使えたりします。）

サンプルコード

#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
using namespace std;

int N;
pair<int, string> a[100009];

int main() {
    // 例 1: N 人の成績と名前を入力して、成績の大きい順にソートする
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> a[i].second; // 名前を入力する
        cin >> a[i].first; // 成績を入力する
    }
    sort(a, a + N, greater<pair<int, string>>());
    for (int i = 0; i < N; i++) {
        cout << "Name = " << a[i].second << ", Score = " << a[i].first << endl;
    }
    return 0;
}

3-19. tuple

3 つ以上の要素から成る「組」を持つことができる型です。pair 型は 2 つですが、tuple 型は何個でも要素を持てます。

概要

tuple 型は、3 つ以上の要素を持てる型です。（※ 1 つとか 2 つでもできます。）
以下の 3 つの構文を覚えておくと、競技プログラミングなどにおいて困ることはほぼ無いと思います。

  • 型 v1, 型 v2, ..., 型 vn を持つ tuple 型変数を定義したい場合、tuple< v1,v2,...,vn > a; という感じのコードを書くと良いです。例えば、int 型, int 型, string 型から成る tuple 型変数を定義したい場合、tuple< int,int,string > a; などと書きます。
  • tuple 型変数 a の i 個目の要素にアクセスしたい場合、get< i >(a) と書けば良いです。0 個目の要素から始まることに注意してください。
  • make_tuple(a1,a2,...,an) で引数のコピーから tuple を生成することができます。（サンプルコードの最後から 6 行目を参照。）

なお、2 つの tuple 型要素の大小比較は、以下のようにして決まります。

  • 0 個目の要素が小さい方を小さいとみなす。
  • 0 個目の要素が同じである場合、1 個目の要素が小さい方を小さいとみなす。
  • 1 個目の要素も同じである場合、2 個目の要素が小さい方を小さいとみなす。（以下続く）

tuple をインクルードすることで使えます。

サンプルコード

#include <iostream>
#include <tuple>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // 例 1: tuple の基本
    tuple<int, int, int> A;
    cin >> get<0>(A) >> get<1>(A) >> get<2>(A);
    cout << get<0>(A) + get<1>(A) + get<2>(A) << endl;
    
    // 例 2: vector にも tuple を入れられます、この例はソートするプログラムです
    vector<tuple<double, int, int>> B; int N;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        double p1; int p2, p3;
        cin >> p1 >> p2 >> p3;
        B.push_back(make_tuple(p1, p2, p3));
    }
    sort(B.begin(), B.end());
    for (int i = 0; i < N; i++) printf("%.5lf %d %d\n", get<0>(B[i]), get<1>(B[i]), get<2>(B[i]));
    return 0;
}

3-20. assert

条件を決めて、それを満たさない場合ランタイムエラーを起こす関数です。後編でも述べますが、デバッグなどに使えます。

概要

assert(条件) と書くことで、条件を満たさない場合にランタイムエラーを起こす関数になります。例えば、$N \leq 20$ の場合のみ実行して、それ以外の場合ランタイムエラーを起こすようにしたい場合、assert(N <= 20) と書けばできます。cassert をインクルードすることで使えます。

サンプルコード

Tips: 競プロでは実行時間制限がおよそ 2 ～ 3 秒のことが多いです。

#include <iostream>
#include <cassert>
using namespace std;

int N, X, cnt, a[10009];

int main() {
    // 例 1: a[i] + a[j] = X を満たす (i, j) [i < j] の個数を列挙する
    // N > 10000 の場合実行時間が間に合わない（TLE する）のでランタイムエラーを起こすようにする
    
    cin >> N >> X;
    for (int i = 1; i <= N; i++) cin >> a[i];
    assert(N <= 10000);
    
    for (int i = 1; i <= N; i++) {
        for (int j = i + 1; j <= N; j++) {
            if (a[i] + a[j] == X) cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

3-21. count

配列や vector のある区間の要素の中で、x がいくつ含まれるかを返す関数です。

概要

ここでは、a を配列とします。そのとき、count(a + l, a + r, x) は a[l], a[l+1], ..., a[r-1] の中で、x となるようなものの個数を整数型で返します。vector の場合、count(v.begin(), v.end(), x) のように書けばよいです。
計算量は $O(r-l)$ です。algorithm をインクルードすることで使えます。

サンプルコード

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

int main() {
    // 例 1: 配列 a に含まれる 1 の個数、2 の個数を出力する（それぞれ　4, 3 と出力されます）
    int a[10] = {1, 2, 3, 4, 1, 2, 3, 1, 2, 1};
    cout << count(a, a + 10, 1) << endl;
    cout << count(a, a + 10, 2) << endl;

    // 例 2: b[1], b[2], ..., b[N] を受け取り、その後 Q 個の質問を受け取る。
    // 各質問に対し、b[l], b[l+1], ..., b[r] の中で x が何個あるかを出力する。
    int b[1009], N, Q;
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> b[i];
    cin >> Q;
    for (int i = 1; i <= Q; i++) {
        int l, r, x;
        cin >> l >> r >> x;
        cout << count(b + l, b + r + 1, x) << endl;
    }
    return 0;
}

3-22. find

配列や vector のある区間の要素の中に x が含まれるか、含まれる場合はどこにあるかを返す関数です。

概要

a を配列とします。そのとき、find(a + l, a + r, x) は、以下のイテレーターを返します。

  • a[l], a[l+1], ..., a[r-1] の中に x が含まれない場合は a + r のイテレーター。
  • そうでない場合は、a[l] から順に見ていったときに初めて a[i] = x となるような a[i] のイテレーター。

a が vector の場合にも使えます。find(a.begin(), a.end(), x) とすると、関数は以下のイテレーターを返します。

  • a[0], a[1], ..., a[a.size() - 1] の中に x が含まれない場合　a.end()。
  • そうでない場合、初めて a[i] = x となるような a[i] のイテレーター。

なお、find 関数はイテレーターを返しますが、初めて現れる位置を知りたい場合は、find(a + l, a + r, x) - a のように書くと、「初めて x が現れるのは配列の何番目の要素か」を返します。計算量は $O(r - l)$ です。algorithm をインクルードすることで使えます。

サンプルコード

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

int main() {
    // 例 1: a[1], a[2], ..., a[N] を受け取る。その後、Q 個の質問を受け取る。
    // 各質問は (l, r, x) の組から成り、a[l], a[l+1], ..., a[r] の中で x が存在しない場合 -1
    // そうでない場合、存在する位置（ポインタではない）を出力する。
    int N, Q, a[1009];
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> a[i];
    cin >> Q;
    for (int i = 1; i <= Q; i++) {
        int l, r, x;
        cin >> l >> r >> x;
        int f = find(a + l, a + r + 1, x) - a;
        if (f == r + 1) cout << "-1" << endl; // 存在しない場合
        else cout << f << endl; // 存在する場合
    }
    return 0;
}

3-23. next_permutation

次の順列を生成する関数です。

概要

next_permutation(a, a + n) を使って、while ループを回す感じでやります。
下のコードを見た方がわかりやすいと思います。

// 配列の場合
int n, a[109]; cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
do {
    for (int i = 0; i < n; i++) {
        if (i) cout << ",";
        cout << a[i];
    }
    cout << endl;
} while(next_permutation(a, a + n));

while 文は、次の順列が存在しないとき（それより辞書順で大きいような順列が存在しないとき）に抜けます。例えば、n = 3, a = {2, 3, 1} で実行した場合の出力結果は以下のようになります。

2,3,1
3,1,2
3,2,1

すべての順列を回したい場合は、a = {1, 2, 3, ..., n} など、小さい順に並んでいる状態にしてください。 また、vector で next_permutation を使いたい場合は、next_permutation(a.begin(), a.end()) のようにしてください。

順列の長さを $N$ とするとき、次の順列を生成するのに計算量最大 $O(N)$ かかります。
また、{$1, 2, 3, ..., N$} とソートされている場合は、$N!$ 回 while 文の中をループします。
algorithm をインクルードすると使えます。

サンプルコード

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

int N, A[12][12], B[12], perm[12], ans = 2000000000;

int main() {
    // N 個の都市があり、都市 i から j まで移動するのにかかる時間は A[i][j] 分
    // 全ての都市を訪れるのに何分かかるか？　ただし、どの都市から出発、どの都市に到着してもよい。
    // A[i][j] = A[j][i], A[i][i] = 0
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) cin >> A[i][j];
    }
    for (int i = 0; i < N; i++) B[i] = i + 1;

    do {
        int sum = 0;
        for (int i = 0; i < N - 1; i++) {
            sum += A[B[i]][B[i + 1]];
        }
        ans = min(ans, sum);
    } while(next_permutation(B, B + N));
    
    cout << ans << endl;
    return 0;
}

3-24. __builtin_popcount

整数 x を二進数で表したとき、1 であるようなビットの個数を返す関数です。
この関数は gcc で利用可能ですが、Visual Studio 2019 などでは使えません。

概要

__builtin_popcount(x) は、x の 1 であるようなビットの個数を返す関数です。例えば、x = 42 の場合、42 を 2 進数で表すと 101010 であり、3 個の 1 を含むので、3 を返します。

また、__builtin_popcountll(x) という関数もあって、それは long long 型に対応しています。両方、追加のインクルードファイル無しで使えます。

注記1

Visual Studio 2019 など C++17 が対応されている環境では、__popcnt(x), __popcnt64(x) といった関数が使えます。ただし、intrin.h をインクルードする必要があります。 (コメント を頂きました。)

注記2

bitset でも __builtin_popcount(x) と同じようなことができます。詳しくは 3-25. 節をご覧ください。（コメント を頂きました。）

サンプルコード

#include <iostream>
using namespace std;

int main() {
    // 例 1: x を 2 進数表記したときに、1 であるビットの個数を出力する。
    long long x;
    cin >> x;
    cout << __builtin_popcountll(x) << endl;
    return 0;
}

3-25. bitset

ビット集合を表す型（クラス）です。N 桁の 2 進数だと思うこともできます。
ビット演算を高速に行いたいときなどに使えます。

概要

まず、変数の定義は以下のように行います。

// 例 1: 長さ 250000 の bitset（250000 桁の 2 進数だと思ってよい）を定義する。
bitset<250000> bs1;

// 例 2: 長さ 8 の bitset を定義する。整数から初期化を行う。
bitset<8> bs2(131); // 7 ビット目から 0 ビット目への順番で、10000011 となる。

// 例 3: 長さ 8 の bitset を定義する。2 進数から初期化を行う。
bitset<8> bs3("10000011"); // 7 ビット目から 0 ビット目への順番で、10000011 となる。

// 例 4: 例 3 とやってることは変わらない。ただ bitset の長さが増えただけ。
bitset<2000> bs4("10000011"); // 1999 ビット目から 0 ビット目の順番で、0...010000011 となる。

また、bitset では以下のような処理ができます。（ここでは、a, b を bitset 型の変数とします。）

プログラム 説明
a = (a ^ b) など int 型などと同じように、ビット演算（and, or, xor）をすることができます。
a.set(x) a の $x$ 桁目（$2^x$ の位）を 1 に変更します。
a.reset(x) a の $x$ 桁目（$2^x$ の位）を 0 に変更します。
a[i] 配列と同様、a の $i$ 桁目（$2^i$ の位）にアクセスすることができます。a[i] は必ず 0 か 1 です。
a.count() a の全ての桁のうち、1 となっている桁の個数を返します。__builtin_popcount(x) と似ています。

$N$ ビットの bitset に対して、and, or, xor などのビット演算を行うのにかかる計算量は $\frac{N}{32}$ 回程度と高速です。bitset をインクルードすると使えます。

サンプルコード

#include <iostream>
#include <bitset>
#include <string>
using namespace std;

int main() {
    // 例 1: A or B を計算します。なお、A と B は string 型で 2 進数で与えられます。
    string A; cin >> A;
    string B; cin >> B;
    
    bitset<2000> A1(A);
    bitset<2000> B1(B);
    bitset<2000> ans = (A1 | B1);

    bool flag = false;
    for (int i = 1999; i >= 0; i--) {
        if (ans[i] == 1) flag = true;
        if (flag == true) cout << ans[i];
    }
    cout << endl;
    return 0;
}

# 4. 皆さんの疑問「標準ライブラリ、結局どんな場面で使うのか？」 皆さんの中には、この記事を読んでそう思った方も多いと思います。

今回の 25 個の標準ライブラリはわかったけど、どういう問題やどういうアルゴリズムの実装で活用できるのか？？？

そう思った皆さん。

後編を読みましょう。

後編では、今回説明した標準ライブラリ（STL）を活用できるアルゴリズム、活用できるケースを 11 例紹介します。よろしければ、是非お読みください。

つづく

後編 につづきます。

  1. 便宜上、提出数のデータを示しておりますが、各プログラミング言語毎の参加者数で数えても、C++ は半分程度です。 ↩

  2. 残り 10% は、list・malloc などです。競技プログラミングではそれほど使われない（あるいは同等の実装量で代用できる）と思っているので、本記事には載せませんでした。 ↩

  3. 詳しくは、こちらの記事をご覧ください。 ↩

  4. 厳密には、__gcd, __builtin_popcount の 2 つは標準ライブラリに含まれません。しかし、競プロやアルゴリズム実装において比較的重要なので、含めておきました。 ↩

1107
1070
25

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1107
1070

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?