<jupyter_start><jupyter_text>メモ<jupyter_code># colab でプログラムを作って実行する
# !g++ temp.cpp; echo  |./a.out
%%writefile temp.cpp
# include <bits/stdc++.h>
using namespace std;
int main () {cout << "Hello World!" << endl;}
!g++ temp.cpp; echo  |./a.out<jupyter_output>Hello World!<jupyter_text>厳選！C++ アルゴリズム実装に使える 25 の STL 機能【前編】厳選！C++ アルゴリズム実装に使える 25 の STL 機能【後編】たのしい探索アルゴリズムの世界【前編：全探索、bit全探索から半分全列挙まで】 たのしい探索アルゴリズムの世界【前編：全探索、bit全探索から半分全列挙まで】 の 3 章アルゴリズムを勉強するなら二分探索から始めよう！ 『なっとく！アルゴリズム』より二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜二分法とは？ アルゴリズム・収束・例題DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【後編】BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～区間 DP を勉強してみた - Kutimoti の競プロメモビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜Educational DP Contest | AtCoder最短経路問題総特集！！！～BFSから拡張ダイクストラまで～ by @ageprocpp最短経路問題総特集！！！～BFSから拡張ダイクストラまで～最小全域木問題 (クラスカル法とプリム法)Kruskal法をココロから納得する | けんちょんの競プロ精進記録「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜累積和を何も考えずに書けるようにする！いもす法グラフ理論の基礎 by @maskot1977木構造｜木とは/木の表現/2分探索木Union-Find木の解説と例題 by @ofutonfuton分野別 初中級者が解くべき過去問精選 100 問AIZU ONLINE JUDGE - Introduction to Algorithms and Data Structure (ALDS)非情報系学生のための C/C++ 入門AIZU ONLINE JUDGE - Introduction To Programming Iアルゴリズムとは何か！？ ～ 文系理系問わず楽しめる精選 6 問 ～ by @drken「AtCoder Beginners Selection」AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ by @drken計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜ソートを極める！ 〜 なぜソートを学ぶのか 〜 ---ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【上級編：目指せレッドコーダー！】<jupyter_code># AtCoder のレーティング
%%html
<style>
    tr td:nth-child(2) {
        color: red;
        text-align: center;
    }
</style>
<table border="1">
<thead>
<tr><th>レーティング</th><th style="width:10%" align="center">色</th><th>相対的な位置</th><th>絶対的な位置</th></tr>
</thead>
<tbody>
<tr><td>2800+</td><td>赤</td><td>上位 0.2%</td><td></td></tr>
<tr><td>2400-2799</td><td>橙</td><td>上位 0.6%</td><td></td></tr>
<tr><td>2000-2399</td><td>黄</td><td>上位 2%</td><td>アルゴリズムの研究職・研究開発で重宝されるレベル</td></tr>
<tr><td>1600-1999</td><td>青</td><td>上位 5%</td><td>ほとんどのIT企業でアルゴリズム能力がカンストする</td></tr>
<tr><td>1200-1599</td><td>水</td><td>上位 10%</td><td>半数以上のIT企業でアルゴリズム能力がカンストする</td></tr>
<tr><td>800-1199</td><td>緑</td><td>上位 20%</td><td>エンジニアとしてかなり優秀</td></tr>
<tr><td>400-799</td><td>茶</td><td>上位 35%</td><td>学生なら優秀</td></tr>
<tr><td>1-399</td><td>灰</td><td>上位 100%</td><td>学生なら優秀</td></tr>
</tbody>
</table>
# AtCoder の過去問を解ける便利なサイト => AtCoder Problems
# 競プロにおける C++ のすすめ
# AtCoder ユーザーの半数以上が C++ を使っている
# AtCoder 公式解説のソースコード、解説記事のソースコードの大半が C++ である。
# プログラミングコンテストチャレンジブック（蟻本）、
# プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
# 実行速度が他の言語に比べて高速であるため、競プロに有利である
# 問題
# 整数 A と B が与えられます。
# そのとき、縦 A センチ、横 B センチの長方形の周の長さを整数で出力してください。
# 1≤ A, B ≤ 100
# 例 4 5 => 18
# 1 9 => 20
# 6 7 => 26
# 31 27 => 116
# 100 100 => 400
%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b; cin >> a >> b;
    cout << (a + b) * 2 << endl;
}
!g++ temp.cpp; echo 4 5 |./a.out #=> 18
!g++ temp.cpp; echo 1 9 |./a.out #=> 20
!g++ temp.cpp; echo 6 7 |./a.out #=> 26
!g++ temp.cpp; echo 31 27 |./a.out #=> 116
!g++ temp.cpp; echo 100 100 |./a.out #=> 400
# 全てに正解になる必要がある
# 効率を考える必要がある
# 問題
# N 枚のカードが一列に並べられています。
# 左から i 番目のカードには、整数 A_i が書かれています。
# あなたは N 枚のカードの中から 2 枚同時に選び、取ることができます。
# 取った 2 枚に書かれた整数の合計がちょうど 101 となるような、カードの選び方の通り数を求めてください。
# 1≤ N ≤ 10^6, 1≤ Ai ≤10^9
# 「何枚目と何枚目を選ぶか全探索する」
# という方法だと思います。つまり、1 ≤ i < j ≤ N を満たすすべての (i,j) の組を全探索し、
# A_i + A_ j=101 となる通り数を数え上げるという方法です。
# しかし、その解法の場合、N^2 回程度のループを回す必要があります。 N ≤ 10^6 なので、
# 最大 10^12 回程度のループを回す必要があります。しかし、競技プログラミングにおいて、
# およそ 10^8 ～ 10^9 回を超える回数のループをした場合、実行時間超過 (TLE) となり、
# 1 ケースでも TLE を起こすと不正解となってしまいます。

# そのため、より効率的なアルゴリズムを実装することが求められます。
# 例えば、本問題であれば、以下のような解法を使うと、
# 高々 N 回程度のループでプログラムの実行が終わります。

# A_i ≥ 101 のカードはすべて無視する。
# A_i = 1, A_i = 2, ..., A_i = 100 のカードの枚数を数える。
# それぞれ c_1, c_2, ..., c_100 とする。
# そのとき、
# (c1×c100)+(c2×c99)+(c3×c98)+...+(c50×c51)
# が答えである。

# C++ での実装例 <= 分からないが動かすことは出来た。先へ進む

%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N; cin >> N;
    vector<int> A(1000009);
    vector<int> cnt(109);
    for (int i = 0; i < N; i++) {
        cin >> A.at(i);
        if (A.at(i) <= 100) cnt.at(A.at(i))++;
    }
    int Answer = 0;
    for (int i = 0; i < 50; i++) Answer += cnt.at(i) * cnt.at(101 - i);
    cout << Answer << endl;
}
!g++ temp.cpp; echo 2 1 1 |./a.out #=> 0
!g++ temp.cpp; echo 2 1 100 |./a.out #=> 1
!g++ temp.cpp; echo 5 1 2 3 6 95 |./a.out #=> 1
!g++ temp.cpp; echo 5 1 100 2 3 95 |./a.out #=> 1
!g++ temp.cpp; echo 5 1 2 3 4 95 |./a.out #=> 0
# 問題 AtCoder Beginner Contest 145 A - Circle
# 整数 r が与えられます。
# 半径 r の円の面積は半径 1 の円の面積の何倍か、整数で出力してください。
# つまり r×r を出力してください。
%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
    int r; cin >> r;
    cout << r * r << endl;
}
# 「どのようにしてコードを書けば良いか」分からない人も多いです。
# そこで、一つの例として、C++ を学習できる便利なサイトを紹介します。
# 非情報系学生のための C/C++ 入門
# 提出結果のエラーコード WA などの意味
%%html
<style>
    tr td:nth-child(1) {
        color: red;
        text-align: center;
    }
</style>
<table border="1">
<thead>
<tr><th>提出結果</th><th>意味</th></tr>
</thead>
<tbody>
<tr><td>AC</td><td>正解です。やったね！</td></tr>
<tr><td>WA</td><td>出力が間違っているようなテストケースがあります。</td></tr>
<tr><td>TLE</td><td>実行時間制限以内にプログラムの実行が終わらなかったテストケースがあります。</td></tr>
<tr><td>RE</td><td>プログラムがランタイムエラー（実行時エラー）を起こしたテストケースがあります。</td></tr>
<tr><td>WJ</td><td>現在採点が行われております。しばらくお待ちください。</td></tr>
</tbody>
</table>
# 全探索に慣れる！
# 問題 くじびき
# 数字が書かれている N 枚の紙切れが袋に入っています。あなたはこの袋から紙切れを取り出し、
# 数字を見て袋に戻すということを 4 回行い、4 回の数字の和が M になっていれば、あなたの勝ちです。
# 紙切れに書かれている数字が {K_1, K_2, ..., K_N} である場合、あなたが勝つような可能性はありますか。
# 制約：N ≤ 50, M ≤ 10^8, Ki ≤10^8
# これは、1 回目に K_a、2 回目に K_b、3 回目に K_c、4 回目に K_d を取り出すとして、
# (a,b,c,d) のあり得る組を全通り調べる（四重ループをする）と解けます。N^4 回程度の計算が必要ですが、
# N ≤ 50  なので、およそ 50^4 ≒ 6.25×10^6 回のループしか回す必要がなく、実行時間制限には余裕をもって間に合います。
%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;
int main () {
    int n, m; cin >> n >> m;
    vector<int> vec(n);
    for (int i=0; i < n ; i++) {
        cin >> vec.at(i);
    }
    bool ans = false;
    
    for (int i=0; i < n ; i++) {
        for (int j=0; j < n ; j++) {
            for (int k=0; k < n ; k++){
                for (int l=0; l < n ; l++){
                    if (vec.at(i)+vec.at(j)+vec.at(k)+vec.at(l) == m) ans = true;
                }
            }
        }
    }
    if (ans) cout << "Yes" << endl;
    else cout << "No" << endl;
}
!g++ temp.cpp; echo 3 10 1 3 5 |./a.out #=> Yes 1 1 3 5
!g++ temp.cpp; echo 3 9 1 3 5 |./a.out #=> No 
!g++ temp.cpp; echo 3 9 1 3 2 |./a.out #=> Yes 3 3 2 2
# 実験 重複あり全探索 => ネットにあった例
%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;

vector<int> buf;

void dfs(int i, const int size, const int range_start, const int range_end)
{
    if (i == size) {
        // ここで所望の作業を行う
        for(int i = 0; i < buf.size(); ++i){
            cout << buf[i] << " ";
        }
        cout << endl;
    }
    else{
        for(int j = range_start; j <= range_end; ++j){
            buf[i] = j;
            dfs(i + 1, size, range_start, range_end);
        }
    }
}

int main(void)
{
    int size = 3;
    int range_start = 1;
    int range_end = 5;
    
    buf.resize(size);
    dfs(0, size, range_start, range_end);
}
!g++ temp.cpp; ./a.out
# 4 種類の全探索
# 本当に全通り調べ上げる「全探索」大体の場合、多重ループで解けます。
# 工夫して探索の通り数を減らす「全探索」
# ビット全探索 多重ループではうまくいかない全探索の 1 つです。詳しくは、こちらの記事を参照してください。
# 順列全探索 多重ループではうまくいかない全探索の 1 つです。詳しくは、こちらの記事を参照してください。

# 全探索の問題 <= あとでやろう ABC = AtCoder Beginner Contest 
# ABC144 B - 81 基礎の基礎です。
# ABC150 B - Count ABC 全探索というか、「全通り調べ上げます」。
# ABC122 B - ATCoder これも基本です。
# ABC136 B - Uneven Numbers これも基本です。
# ABC106 B - 105 これも基本です。
# ABC120 B - K-th Common Divisors 単純な考察が必要ですが、基本です。
# ABC057 C - Digits in Multiplication 探索通り数を頑張って減らします。
# ABC095 C - Half and Half 探索通り数を頑張って減らします。
# 三井住友信託銀行プログラミングコンテスト2019 D - Lucky PIN 探索通り数を頑張って減らします。
# ABC128 C - Switches ビット全探索の基本です。
# ABC147 C - HonestOrUnkind2 ビット全探索の基本です。
# ABC145 C - Average Length 順列全探索の基本です。
# ABC150 C - Count Order 順列全探索で解けます。
# ABC054 C - One-stroke Path 順列全探索で解けます。

# 最後に、最も重要なことを書きます。これは、コンテストに出場することです。

# モチベ管理こそが重要
# C++ の場合、使えてほしい STL は以下の 25 個。
%%html
<table border="1">
<tbody>
<tr><td>abs</td><td>sin/cos/tan</td><td>string</td><td>min/max</td><td>swap</td></tr>
<tr><td>__gcd</td><td>rand</td><td>clock</td><td>reverse</td><td>sort</td></tr>
<tr><td>vector</td><td>stack</td><td>queue</td><td>priority_queue</td><td>map</td></tr>
<tr><td>lower_bound</td><td>set</td><td>pair</td><td>tuple</td><td>assert</td></tr>
<tr><td>count</td><td>find</td><td>next_permutation</td><td>__builtin_popcount</td><td>bitset</td></tr>
</tbody>
</table>
# 以下に書かれている、基本的なアルゴリズムとデータ構造を全て理解する。

# アルゴリズム（12 個）

# 全探索（bit 全探索、順列全探索を含む）
# 二分探索
# 深さ優先探索（DFS）
# 幅優先探索（BFS）
# 動的計画法（bitDP などを含む）
# ダイクストラ法（最短経路問題）
# ワーシャルフロイド法（最短経路問題）
# クラスカル法（最小全域木問題）
# 高速な素数判定法
# べき乗を高速に計算するアルゴリズム
# 逆元を計算するアルゴリズム
# 累積和

# データ構造（3 個）

# グラフ（グラフ理論）
# 木
# Union-Find
# 絶対値 abs
%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    // 例 1: 2 つの小数 a と b を入力し、a-b の絶対値を小数で出力します。
    double a, b;
    cin >> a >> b;
    printf("%.12lf\n", abs(a - b)); // lf は double こと
    cout << fixed << setprecision(12) << abs(a - b) << endl;
}
!g++ temp.cpp; echo 2.81 -1.2 |./a.out
# 上のプログラムの cout バージョン
# fixed と setprecision を同時に使う事によって小数点以下の桁数を決められる
# 絶対値 abs
%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    // 例 1: 2 つの小数 a と b を入力し、a-b の絶対値を小数で出力します。
    double a, b;
    cin >> a >> b;
    cout << fixed << setprecision(3) << abs(a - b) << endl;
    printf("%.3lf\n", abs(a - b));
}
!g++ temp.cpp; echo 2.81 -1.2 |./a.out
# 三角関数 sin/cos/tan
# 弧度法を使う
# sin(x) の値を double 型で返す => sin(π/6) = 0.5。
# cos(x) の値を double 型で返す => cos(π/6) = 0.866025... 
# tan(x) の値を double 型で返す => tan(π/6) = 0.577350... 
%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    // 度数法で角度を入力し、計算する
    double pi = M_PI;
    double x;
    cin >> x;
    double y = x / 180.0 * pi;
    cout << y << endl;
    printf("%.12lf\n", sin(x / 180.0 * pi)); // lf は double のこと , long float の意か?
    printf("%.12lf\n", cos(x / 180.0 * pi));
    printf("%.12lf\n", tan(x / 180.0 * pi));
    cout << fixed << setprecision(12);
    cout << sin(y) << endl;
    cout << cos(y) << endl;
    cout << tan(y) << endl;
}
!g++ temp.cpp; echo 30 |./a.out
# 実験 setprecision にデフォルトはあるか => ない
%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    cout << M_PI << endl;
    cout << setprecision(16) << M_PI << endl;
    cout << setprecision(16) << M_PI*1000 << endl;
    cout << setprecision(16) << M_PI/1000 << endl;
    double x = Mi_PI;
    cout << fixed << setprecision(12); // fixed と併用すると小数点以下が決められる
    cout << sin(M_PI/6) << endl;
    cout << cos(M_PI/6) << endl;
    cout << tan(M_PI/6) << endl;
}
!g++ temp.cpp; echo  |./a.out
# 実験 to_string の桁数 
# cout の小数点以下の桁数を固定にする方法
%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;

template <typename T>
std::string to_string_with_precision(const T a_value, const int n = 6)
{
    std::ostringstream out;
    out.precision(n);
    out << std::fixed << a_value;
    return out.str();
}

int main() {
    cout << M_PI << endl; // 有効桁数 6 桁 => 3.14159
    cout << M_PI/1000 << endl; // 有効桁数 6 桁 => 0.00314159
    cout << to_string(M_PI) << endl; // 小数点以下 6 桁で固定  => 3.141593
    cout << to_string(M_PI/1000) << endl; // 小数点以下 6 桁で固定 => 0.003142
    cout << to_string_with_precision(M_PI, 12) << endl; // 小数点以下 12 桁を指定 => 3.141592653590
    cout << to_string_with_precision(M_PI/1000, 12) << endl; // 小数点以下 12 桁を指定 => 0.003141592654
}
!g++ temp.cpp; echo  |./a.out
# string
%%writefile temp.cpp
#include <bits/stdc++.h>
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.at(i) = 'z';
    cout << s << endl;
    return 0;
}
!g++ temp.cpp; echo "try" "012345" "012345"|./a.out
# 上のプログラムを日本語対応にしてみる
%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;

int count_byte(char c){
    if ((c & 0x80) == 0) return 1;
    else if ((c & 0xe0) == 0xc0) return 2;
    else if ((c & 0xf0) == 0xe0) return 3;
    else return 4;
}

vector<string> str2vec(string &str){
    vector<string> vec;
    for (int i = 0 ; i < str.size(); i += count_byte(str.at(i))){
        vec.push_back(str.substr(i,count_byte(str.at(i))));
    }    
    return vec;
}

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

    // 例 2: 入力した文字列 s の偶数文字目を 'z' に変えて出力します。
    string s;
    cin >> s;
    vector<string> jvec2;
    jvec2 = str2vec(s);
    for (int i = 0; i < jvec2.size(); i += 2) jvec2.at(i) = 'z';
    for (int i = 0; i < jvec2.size(); i++) cout << jvec2.at(i);
    cout << endl;
}
!g++ temp.cpp; echo "施行" "錯誤してみる" "難しいね!!!!"|./a.out
# string
# S.substr(l)	文字列 S の l 文字目から最後の文字までの部分文字列を返す関数です。
# S.substr(l, r)	文字列 S の l 文字目から l+r-1 文字目までの部分文字列を返す関数です。
# なお、文字列は 0 文字目から始まることにご注意ください
# 最小値・最大値 min/max
# 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 関数はイテレーターを返すため、最初に * を付ける必要があります。
%%writefile temp.cpp
#include <bits/stdc++.h>
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;
}
!g++ temp.cpp; echo |./a.out
# 問題 vector の最小値・最大値を求める関数を作る
%%writefile temp.cpp
# include <bits/stdc++.h>
using namespace std;

int myMax(const vector<int>& v) {
    int max = numeric_limits<int>::min();
    for (auto e : v) if (e > max) max = e;
    return max;
}

int myMax02(const vector<int>& vec){
    return *max_element(vec.begin(), vec.end());
}

int myMin(const vector<int>& v) {
    int min = numeric_limits<int>::max();
    for (auto e : v) if (e < min) min = e;
    return min;
}

int myMin02(const vector<int>& vec){
    return *min_element(vec.begin(), vec.end());
}

int main() {
    vector<int> vex = {1, 2, 3, 4, 5};
    assert(myMax(vex) == 5);
    assert(myMax02(vex) == 5);
    assert(myMin(vex) == 1);
    assert(myMin02(vex) == 1);
}
# 値の交換 swap
# swap(a, b) で、変数 a と b の値を入れ替えることができます。
# バブルソートについて知らない人は => ソートを極める！ 〜 なぜソートを学ぶのか 〜
%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    // 2 つの変数 a, b を入れ替え、出力する
    int a = 3, b = 8;
    swap(a, b);
    cout << a << " " << b << endl;

    // バブルソートによって、vector を小さい順に並び替え、出力する
    vector<int> vec {9, 8, 7, 1, 2, 3};
    for (int i = 0; i < vec.size() - 1; i++) {
        for (int j = 0; j < vec.size(); j++) {
            if (vec.at(j) > vec.at(j + 1)) swap(vec.at(j), vec.at(j +  1));
        }
    }
    for (int i = 0; i < vec.size(); i++) cout << vec.at(i) << endl;
}
!g++ temp.cpp; echo |./a.out
# 最大公約数 __gcd
# 2 つの整数 a, b の最大公約数を返す関数です。
# __gcd(8, 16) = 8
# __gcd(234, 217) = 1
# となります。計算量は O(loga)O(log⁡a) なので、とても高速です。
# 最小公倍数を返す標準ライブラリの関数はありませんが、a と b の
# 最小公倍数は a / __gcd(a, b) * b で計算することができます。
# この書き方は、a * b / __gcd(a, b) よりオーバーフローを起こしにくいです。
%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;
int main () {
    cout << __gcd(8,18) << endl;
    cout << 8 / __gcd(8, 18) * 18 << endl;
}
!g++ temp.cpp; echo |./a.out
# 乱数 rand random
# 基本的に、以下の 2 つをセットで覚えておくと良いと思います。
# rand()	0 以上 2^3 −1 以下のランダムな整数を返す関数です。
# srand((unsigned)time(NULL));	おまじないです。main 関数の冒頭にこれを付けると、
# 実行ごとに乱数生成結果が変わります。
# なお、乱数の質が完全とはいえないので、より良質な乱数を生成したい場合は
# メルセンヌ・ツイスタ (C++ では std::mt19937) などを使いましょう。
%%writefile temp.cpp
#include <bits/stdc++.h>
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;
}
!g++ temp.cpp; echo |./a.out
# 実験 メルセンヌ・ツイスタ mt19937
%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;

int main () {
    srand((unsigned)time(NULL));
    cout << rand() << endl;

    random_device rd;
    mt19937 mt(rd());
    cout << mt() << std::endl;
}
!g++ temp.cpp; echo |./a.out
# 問題 ランダムに 4 桁の 36 進数を作成せよ 
# 36 進数とは a-z0-9 で作る文字列とする
%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;

const string str = "0123456789abcdefghijklmnopqrstuvwxyz";

string getDigits () {
    string digits = "";
    for (int i = 0; i < 4; i++) {
        digits.push_back(str[rand()%36]);
    }
    return digits;
}

int main () {
    srand((unsigned)time(NULL));
    for (int i = 0; i < 4; i++) cout << getDigits() << endl;
}
!g++ temp.cpp; echo |./a.out
# 時間計測 clock
# 基本的に、以下の 2 つをセットで覚えておくと良いと思います。
# clock()	プログラム実行開始から何単位時間経過したかを整数で返す関数です。
# CLOCKS_PER_SEC	定数です。環境によって1 秒が何単位時間か異なるので、秒数を知りたいときに使えます。
# つまり、実行開始からの秒数は clock()/CLOCKS_PER_SEC で表されます。
# ちなみに、CLOCKS_PER_SEC の値は gcc の場合 1000000
%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    // 例 1: 実行にかかる時間を計測する
    vector<int> vec;
    int ti = clock(); // start 時間
    for (int i = 1; i <= 100000; i++) vec.push_back(i);
    printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
}
!g++ temp.cpp; echo |./a.out
# 配列を逆順に並び替え 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()) のように書いてください。 
%%writefile temp.cpp
#include <bits/stdc++.h>
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;
}
!g++ temp.cpp; echo 3 1 2 3 |./a.out
# 実験 reverse
%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;

int count_byte(char c){
    if ((c & 0x80) == 0) return 1;
    else if ((c & 0xe0) == 0xc0) return 2;
    else if ((c & 0xf0) == 0xe0) return 3;
    else return 4;
}

vector<string> str2vec(string &str){
    vector<string> vec;
    for (int i = 0 ; i < str.size(); i += count_byte(str.at(i))){
        vec.push_back(str.substr(i,count_byte(str.at(i))));
    }    
    return vec;
}

int main() {
    string str = "abracadabra";
    reverse(str.begin(), str.end());
    cout << str << endl;
    vector<int> vec = {1,2,3};
    reverse(vec.begin(), vec.end());
    for (int i = 0; i < vec.size(); i++) {
        cout << vec.at(i) << " ";
    }
    cout << endl;
    str = "日本語を含むsentense";
    vector<string> jvec;
    jvec = str2vec(str);
    reverse(jvec.begin(), jvec.end());
    for (int i = 0; i < jvec.size(); i++) {
        cout << jvec.at(i) ;
    } cout << endl;
}
!g++ temp.cpp; echo 3 1 2 3 |./a.out
# ソート 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(NlogN) です。なお、string 型のソートでは、辞書式順序で早い方が小さいとみなされます。
%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> vec {8, 3, 7, 1, 4, 6, 2, 5};
    sort(vec.begin(), vec.end(), greater<int>());
    for (int i = 0; i < vec.size(); i++) cout << vec.at(i) << " " ;
    cout << endl;
    sort(vec.begin(), vec.end());
    for (int i = 0; i < vec.size(); i++) cout << vec.at(i) << " " ;
    cout << endl;
}
!g++ temp.cpp; echo  |./a.out
# vector
# vector<int> a;	vector 型の変数 a を定義します。
# a.push_back(x);	a の末尾に x を追加します。
# a.pop_back();	a の末尾の要素が取り除かれます。
# a[i]	a の先頭から数えて i 番目の要素にアクセスできます。
# a.size()	a に現在いくつ要素が入っているか、整数型で返します。
# 計算量は、push_back、pop_back 両方 O(1)と高速です。メモリ使用量も効率的です。

%%writefile temp.cpp
#include <bits/stdc++.h>
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;
}
!g++ temp.cpp; echo  |./a.out
# stack
# スタックというデータ構造を管理できる型です。もの（値）を積み上げたり、
# 一番上のものを取ったりできるデータ構造です。
# stack というデータ構造では、以下の処理ができます。
# stack<int> a;	stack 型の変数 a を定義します。
# 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 の下位互換です

%%writefile temp.cpp
#include <bits/stdc++.h>
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;
} 
!g++ temp.cpp; echo  |./a.out
# queue
# 待ち行列のようなデータ構造を管理できる型です。
# queue<int> a;	queue 型の変数 a を定義します。
# 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) です。
# 幅優先探索や最短経路問題などでこのデータ構造が利用できます。

%%writefile temp.cpp
#include <bits/stdc++.h>
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;
}
!g++ temp.cpp; echo  |./a.out
# 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(logN) です。

# 変数の定義方法がやや特殊なので、書いておきます。以下のように、
# 最も小さい値を取り出したい場合は 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;

%%writefile temp.cpp
#include <bits/stdc++.h>
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;
}
!g++ temp.cpp; echo  |./a.out
# map 連想配列 associative array unordered_map
# どんな「番地」にも書き込める、無限配列のようなデータ構造
# a を map 型の変数、x を適当な型の変数とします。
# 配列と同じように、代入・演算ができます。x は整数型でなくても、文字列型でも vector 型でも何でもありです。
# a.clear()	マップ a を初期化します。
# なお、最初は値がすべて 0（文字列の場合は空文字列）で初期化されています。
# N を今まで map 型変数にアクセスした数とするとき、マップのある特定の番地へのアクセスにかかる計算量は O(logN) 程度です。
# 変数の定義方法がやや特殊なので、書いておきます。基本的に、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;

%%writefile temp.cpp
#include <bits/stdc++.h>
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 と出力される
}
!g++ temp.cpp; echo  |./a.out
# 実験 map 代入による初期化が出来るか
%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    map<int, const char*> mapList = { {1, "a"}, {2, "b"}, {3, "c"}};
    /*
    map<int, const char*>::iterator it = mapList.begin();
    while(it != mapList.end()) {
        printf("key:%d value:%s\n" , it->first , it->second);
        it++;
    } */
    // 次のように書く方が分かりやすいと思う
    for (auto it = mapList.begin(); it != mapList.end(); it++){
        printf("key:%d value:%s\n" , it->first , it->second);
    }
}
!g++ temp.cpp; echo  |./a.out
# map も set も unordered_map と unordered_set があってそちらの方がパーフォーマンスがいい
# map も set も普通の単語なので検索しにくいので、unordered の方を使うのが良いのではないか
# lower_bound
# 二分探索 をすることができる関数
# 配列 a があったとして、a の l 番目から r-1 番目までの要素が小さい順にソートされていたとしましょう。
# そのとき、lower_bound(a+l, a+r, x) - a というプログラムは、
# a[l] から a[r-1] までの中で初めて x 以上となるようなインデックスを返します。
# つまり、l ≤ i ≤ r−1 の中で、x ≤ a となるような最小の i の値を返します。
# 例えば、a = {2, 3, 4, 6, 9, ...} の場合、lower_bound(a, a + 5, 7) - a = 4 となります。
# 計算量は O(log N) です。

%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a {2, 3, 100, 2, 3};
    sort(a.begin(), a.end());
    cout << lower_bound(a.begin(), a.end(), 100) - a.begin() << endl;

    // 例 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;
    */
}
!g++ temp.cpp; echo  |./a.out
# set 集合 unordered_set unordered_multiset
# 集合を管理することができるデータ構造です
# 二分探索したりできます。このようなデータ構造には、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 も同様。）

%%writefile temp.cpp
#include <bits/stdc++.h>
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); // => "End"
    // auto itr1 = Set.lower_bound(30); // => 37
    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++;
    }

}
!g++ temp.cpp; echo 3 1 3 8 |./a.out
# 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; という感じで変数を定義できます。

%%writefile temp.cpp
#include <bits/stdc++.h>
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;
}
!g++ temp.cpp; echo 2 "Bob" 1 "John" 8 |./a.out
# tuple タプル
# 3 つ以上の要素から成る「組」を持つことができる型です。pair 型は 2 つですが、tuple 型は何個でも要素を持てます。
# tuple 型は、3 つ以上の要素を持てる型です。（※ 1 つとか 2 つでもできます。）
# 以下の 3 つの構文を覚えておくと、競技プログラミングなどにおいて困ることはほぼ無いと思います。
# 型 v1, 型 v2, ..., 型 vn を持つ tuple 型変数を定義したい場合、
# tuple< v1,v2,...,vn > a; という感じのコードを書く
# tuple 型変数 a の i 個目の要素にアクセスしたい場合、get<i>(a) と書けば良い
# make_tuple(a1,a2,...,an) で引数のコピーから tuple を生成することができます。

%%writefile temp.cpp
#include <bits/stdc++.h>
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]));
}
!g++ temp.cpp; echo 1 2 3 2 4.3 2 3 1.4 5 4 |./a.out
# assert
# 条件を決めて、それを満たさない場合ランタイムエラーを起こす関数です。デバッグなどに使えます。
# assert(条件) と書くことで、条件を満たさない場合にランタイムエラーを起こす関数になります。
# 例えば、N ≤ 20 の場合のみ実行して、それ以外の場合ランタイムエラーを起こすようにしたい場合、
# assert(N <= 20) と書けばできます。
# Tips: 競プロでは実行時間制限がおよそ 2 ～ 3 秒のことが多いです。

%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, X, cnt = 0;
    vector<int> a(1000);
    cin >> N >> X;
    for (int i = 0; i < N; i++) cin >> a.at(i);
    assert(N <= 10000);

    for (int i = 0; i < N - 1; i++) {
        for (int j = i + 1; j < N; j++) {
            if (a.at(i) + a.at(j) == X) cnt++;
        }
    }
    cout << cnt << endl;

    // 例 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;
}
!g++ temp.cpp; echo 6 8 1 7 2 6 3 5 |./a.out
# 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) です。

%%writefile temp.cpp
#include <bits/stdc++.h>
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;

    int N, Q;
    cin >> N;
    vector<int> b(N);
    for (int i = 0; i < N; i++) cin >> b.at(i);
    cin >> Q;
    for (int i = 0; i < Q; i++){
        int l, r, x;
        cin >> l >> r >> x;
        cout << count(b.begin()+l, b.begin() + r+1, x) << 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;
    }*/
}
!g++ temp.cpp; echo 10 1 2 3 4 1 2 3 1 2 1   2 0 9 1 0 9 2 |./a.out
# 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) です。

%%writefile temp.cpp
#include <bits/stdc++.h>
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; // 存在する場合
    }
}
!g++ temp.cpp; echo 3 2 4 5   1 1 3 2 |./a.out
# next_permutation 順列
# がよくわからないので実験
%%writefile temp.cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<string> vec = {"book", "pencil", "eraser"};
    sort(vec.begin(), vec.end());
    do {
        for (int i = 0; i < vec.size(); i++){
            if (i) cout << ", ";
            cout << vec.at(i);
        }
        cout<<endl;
    } while (next_permutation(vec.begin(), vec.end()));
}
!g++ temp.cpp; echo |./a.out<jupyter_output>book, eraser, pencil
book, pencil, eraser
eraser, book, pencil
eraser, pencil, book
pencil, book, eraser
pencil, eraser, book<jupyter_text>いまここ<jupyter_code># 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()) のようにしてください。

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

# %%writefile temp.cpp
# #include <bits/stdc++.h>
# 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;
# }


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 の xx 桁目（2x2x の位）を 1 に変更します。
a.reset(x)	a の xx 桁目（2x2x の位）を 0 に変更します。
a[i]	配列と同様、a の ii 桁目（2i2i の位）にアクセスすることができます。a[i] は必ず 0 か 1 です。
a.count()	a の全ての桁のうち、1 となっている桁の個数を返します。__builtin_popcount(x) と似ています。
NN ビットの bitset に対して、and, or, xor などのビット演算を行うのにかかる計算量は N32N32 回程度と高速です。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 個の標準ライブラリはわかったけど、どういう問題やどういうアルゴリズムの実装で活用できるのか？？？

そう思った皆さん。

後編を読みましょう。
厳選！C++ アルゴリズム実装に使える 25 の STL 機能【後編】
後編では、今回説明した標準ライブラリ（STL）を活用できるアルゴリズム、活用できるケースを 11 例紹介します。よろしければ、是非お読みください。

つづく
後編 につづきます。

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

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

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

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



e869120
E869120
@e869120
東京大学 1 年の米田（E869120）です。 AtCoder・CodeForces でレッドコーダーです。国際情報オリンピックにも出場しています。競技プログラミング関連のことを記事にしていきます。よろしくお願い致します。 著書『「アルゴリズム×数学」が基礎からしっかり身につく本』 https://amazon.co.jp/dp/4297125218/
フォロー中


関連記事 Recommended by 

標準ライブラリ
by bestfitat


C++のつまずきポイント解説 その1
by _EnumHack

C++Siv3D入門講座 Vol.06 イテレータ・vector要素の削除
by yagiri000

厳選！Ruby アルゴリズム実装に使える 25 の 標準ライブラリ【前編】
by superrino130

Kaggleで得たスキルを業務で活かす。Kaggleを楽しみながら活用するためのポイント
PR 日立

サントリー「脚の老化対策」4860円OFF！1世帯様1回限り
PR サントリー

この記事は以下の記事からリンクされています
akidon0000
[競技プログラミング] C++ チートシート 灰〜茶まで
からリンク
1 year ago
e869120
AtCoder での実力アップを目指そう！　～競プロ典型 90 問～
からリンク
1 year ago
e869120
情報オリンピックへのいざない　～日本一の競技プログラマーを決める戦い～
からリンク
1 year ago
e869120
実装力で戦える！　～競プロにおける実装テクニック14選～
からリンク
1 year ago
e869120
たのしい探索アルゴリズムの世界【後編：探索手法で実社会の様々な問題を斬る！】
からリンク
1 year ago
過去の16件を表示する
コメント<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1874890835142351, 'fraction_numerical': 0.048656336552137136, 'mean_word_length': 3.204133011643764, 'pattern_counts': {'":': 2, '<': 826, '<?xml version=': 0, '>': 519, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '231095', 'license': 'MIT', 'n_tokens_mistral': 25597, 'n_tokens_neox': 23749, 'n_words': 4527, 'path': 'cpp_atcoder100.ipynb', 'repo_name': 'kalz2q/myjupyternotebooks', 'size': '40077'}