『C++入門 AtCoder Programming Guide for beginners (APG4b)』を読みながら取ったメモ

C++ 競技プログラミング

atcoder.jp

こちらの教材を読みながら問題も解いた．学びになった項目をメモした．

T - 2.03.多次元配列

縦の要素数を取得するには変数名.size()として、横の要素数を取得するには変数名.at(0).size()とします。

U - 2.04.参照

複数の返り値を得る

通常は関数の結果を返り値を使って呼び出し元に返します。 返り値は1つしか返すことができませんが、関数によっては結果を複数返したい場合があります。 このような場合の1つの実現方法として配列に結果を入れて返すという方法があります。別の方法として、参照の引数を用いて結果を返す方法があります。

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

// a,b,cの最大値、最小値をそれぞれminimumの参照先、maximumの参照先に代入する
void min_and_max(int a, int b, int c, int &minimum, int &maximum) {
 minimum = min(a, min(b, c));  // 最小値をminimumの参照先に代入
 maximum = max(a, max(b, c));  // 最大値をmaximumの参照先に代入
}

int main() {
 int minimum, maximum;
 min_and_max(3, 1, 5, minimum, maximum);  // minimum, maximumを参照渡し
 cout << "minimum: " <<  minimum << endl;  // 最小値
 cout << "maximum: " <<  maximum << endl;  // 最大値
}

無駄なコピーを減らす

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

// 配列の先頭100要素の値の合計を計算する
int sum100(vector<int> a) {
 int result = 0;
 for (int i = 0; i < 100; i++) {
   result += a.at(i);
 }
 return result;
}

int main() {
 vector<int> vec(10000000, 1);  // すべての要素が1の配列

 // sum100 を500回呼び出す
 for (int i = 0; i < 500; i++) {
   cout << sum100(vec) << endl;  // 配列のコピーが生じる
 }
}

// 上記の実行は約8000ms

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

// 配列の先頭100要素の値の合計を計算する (参照渡し)
int sum100(vector<int> &a) {
 int result = 0;
 for (int i = 0; i < 100; i++) {
   result += a.at(i);
 }
 return result;
}

int main() {
 vector<int> vec(10000000, 1);  // すべての要素が1の配列

 // sum100 を500回呼び出す
 for (int i = 0; i < 500; i++) {
   cout << sum100(vec) << endl;  // 参照渡しなので配列のコピーは生じない
 }
}

// 上記の実行は約20ms

範囲 for 文

vector<int> a = {1, 3, 2, 5};
for (int x : a) {
 x = x * 2;
}
// aは{1, 3, 2, 5}のまま

vector<int> a = {1, 3, 2, 5};
for (int &x : a) {
 x = x * 2;
}
// aは{2, 6, 4, 10}となる

V - 2.05.再帰関数

再帰関数の実装方法

  1. 「引数」「返り値」「処理内容」を決める
  2. 再帰ステップの実装
  3. ベースケースの実装

Z - 3.02.pair／tupleとauto

tuple も pair も sort 関数で1番目の要素を基準にソート可能．1番目の要素以外も1番目のソート結果に連動して順番が変わる．

make_tuple() で tuple を作成可能

AA - 3.03.STLのコンテナ

定期的に読み直す

AC - 3.05.ビット演算

C++でビット列を扱うには bitset を用います。

bitset<ビット数> 変数名;  // すべてのビットが0の状態で初期化される
bitset<ビット数> 変数名("ビット列(長さはビット数に合わせる)");  // 指定したビット列で初期化される

「ビット数」の部分は定数でなければならず、変数を使うことはできないことに注意してください。

位置の指定についてですが、ビット列の右から左にかけて0, 1, 2, ...と対応します。 配列の位置の指定とは逆になっていることに注意してください。

ビット演算に用いる演算子は優先順位が低いものが多いので、明示的に()でくくる必要がある場合があります。

AD - 3.06.その他の機能

char型に対する加算

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

int main() {
 for (int i = 0; i <= ('Z' - 'A'); i++) {
   cout << (char)('A' + i);
 }
}

大文字⇔小文字変換

(char)('x' + ('A' - 'a')) // 'X' 小文字→大文字
(char)('X' - ('A' - 'a')) // 'x' 大文字→小文字

char型の比較

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

int main() {
 char c = 'X';
 if ('A' <= c && c <= 'Z') {
   cout << "YES" << endl;
 }
 else {
   cout << "NO" << endl;
 }
}

const修飾子の使いどころ

「const修飾子を付けた変数」を使えば直接数値を書くこと無く、楽かつ安全にbitsetのビット数を指定できます。

const int B = 100;

bitset<B> func1(bitset<B> a) {
 ...
}
bitset<B> func2(bitset<B> a) {
 ...
}

条件演算子

条件式 ? 真の時の式 : 偽の時の式

例

int c = a < b ? a : b;

条件演算子はネストできる

int answer = a < b && a < c ? a : b < a && b < c ? b : c;

ネストすると読みにくいので，

// インデントのパターンその1
int answer = a < b && a < c
 ? a 
 : b < a && b < c
   ? b 
   : c;

// インデントのパターンその2
int answer = a < b && a < c ? a 
 : b < a && b < c ? b 
 : c;

と書くと良い．

AH - 4.03.テンプレート

template <typename テンプレート引数>
返り値の型 関数名(引数の型 引数...(必要な分だけ書く)) {
 // 処理内容
}

サンプル

// xの二乗を返す (関数テンプレート版)
template <typename T>
T square(T x) {
 return x * x;
}

『競プロのための標準 C++』を読みながら取ったメモ

C++ 競技プログラミング

zenn.dev

こちらの書籍を読みながら知らなかった項目を実装しながらメモ．

01 string

  • string型で宣言した変数は初期化しなければカラ．サイズは0．
  • string 変数名(n，char型) でchar型の文字をn回繰り返した文字列で初期化できる．
  • stoiでstring型からint型に変換できるが，文字列が"1101"などの二進数文字列の場合，stoi(string, nullptr, 基数) でパースして整数変換できる．
  • .push_back(char型) で末尾に1文字追加，.pop_back()で末尾の1文字削除
  • 文字列の基本の順番は 0 < 9 < A < Z < a < z （参考：ASCIIコード表）で，辞書形式の順番になる．
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    string s;
    cout << s << endl;
    cout << s.size() << endl;
    //output
    //
    // 0

    string s5(5, 'a');
    cout << s5 << endl;
    cout << s5.size() << endl;
    //output
    // aaaaa
    // 5

    s = "1101";
    int ss = stoi(s, nullptr, 2);
    cout << ss << endl;
    //output
    // 13

    s = "test";
    s.push_back('a');
    cout << s << endl;
    s.pop_back();
    cout << s << endl;
    //output
    // testa
    // test

    vector<string> sv;
    sv.push_back("Ca");
    sv.push_back("ab");
    sv.push_back("Ab");
    sv.push_back("cA");
    sort(sv.begin(), sv.end());
    for (size_t i = 0; i < sv.size(); i++)
    {
        cout << sv[i] << endl;
    }
    //output
    // Ab
    // Ca
    // ab
    // cA


    return 0;
}

02 vector

  • 初期化
    • vector<Type> 変数名(n, Type(value)) でn個のType(value)の値で初期化
    • valueを指定しない場合（Type()）は各型0や0.0，空文字列，falseなどで初期化
    • nも指定しないで vector<Type> 変数名 で定義した場合は要素数0の空配列
  • .empty()で空チェック
  • string型同様，.push_back(), .pop_back()で末尾の追加・削除
  • vector<bool> のみ，.flip() で true/false の反転ができる
  • （vector関連ではないが，cout << boolalpha でbool型の出力を0/1ではなくtrue/falseで表示できる）
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);


    vector<int> nums(5, 100);
    cout << nums.size() << endl;
    for (size_t i = 0; i < nums.size(); i++)
    {
        cout << nums[i] << endl;
    }
    //output
    // 5
    // 100
    // 100
    // 100
    // 100
    // 100

    vector<int> nums_test1(3);
    cout << nums_test1.size() << endl;
    for (size_t i = 0; i < nums_test1.size(); i++)
    {
        cout << nums_test1[i] << endl;
    }
    vector<string> nums_test2(2);
    cout << nums_test2.size() << endl;
    for (size_t i = 0; i < nums_test2.size(); i++)
    {
        cout << nums_test2[i] << endl;
    }
    //output
    // 3
    // 0
    // 0
    // 0
    // 2
    //
    //


    vector<int> empty1(3, 1);
    cout << empty1.empty() << endl;
    vector<int> empty2;
    cout << empty2.empty() << endl;
    //output
    // 0(false)
    // 1(true)

    vector<int> pushpopback {5, 10, 3};
    pushpopback.push_back(100);
    for (size_t i = 0; i < pushpopback.size(); i++)
    {
        cout << pushpopback[i] << endl;
    }
    //output
    // 5
    // 10
    // 3
    // 100
    pushpopback.pop_back();
    for (size_t i = 0; i < pushpopback.size(); i++)
    {
        cout << pushpopback[i] << endl;
    }
    //output
    // 5
    // 10
    // 3

    vector<bool> booleans_test = {false, true, false};
    booleans_test.flip();
    for (size_t i = 0; i < booleans_test.size(); i++)
    {
        cout << boolalpha << booleans_test[i] << endl;
    }
    //output
    // true
    // false
    // true

    return 0;
}

03 numeric

  • accumurate(イテレータ最初, イテレータ最後, 初期値, binary_op) で初期値に対して配列の累積和を計算
  • 上記で binary_op を指定した場合はその計算を行いながら処理する（例えば string(), multiplies() など）
  • iota(イテレータ最初, イテレータ最後, 初期値) で初期値から1ずつ増やした値を各要素にセットする．
  • 上記で初期値を 'a' にセットすれば a から順にアルファベットをセットした配列を作れる（ただし，vectorのTypeはcharで定義すること）
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    vector<int> vec = {1, 2, 3, 4, 5};
    int s = accumulate(vec.begin(), vec.end(), 0);
    cout << s << endl;
    s = accumulate(vec.begin(), vec.end(), 100);
    cout << s << endl;
    //output
    // 15
    // 115

    vector<string> vec2 = {"apple", "orange", "peach"};
    string s2 = accumulate(vec2.begin(), vec2.end(), string());
    cout << s2 << endl;
    s2 = accumulate(vec2.begin(), vec2.end(), string("header_"));
    cout << s2 << endl;
    //output
    // appleorangepeach
    // header_appleorangepeach

    s = accumulate(vec.begin(), vec.end(), 1, multiplies<>());
    cout << s << endl;
    //output
    // 120


    iota(vec.begin(), vec.end(), 11);
    for (size_t i = 0; i < vec.size(); i++)
    {
        cout << vec[i] << endl;
    }
    //output
    // 11
    // 12
    // 13
    // 14
    // 15


    vector<char> vec_char(26);
    iota(vec_char.begin(), vec_char.end(), 'a');
    for (size_t i = 0; i < vec_char.size(); i++)
    {
        cout << vec_char[i] << endl;
    }
    //output
    // a
    // b
    // .................
    // z


    return 0;
}

04 unordered_set

そもそも unordered_set を知らなかったのでググった．

主な set との違いを unordered_set - cpprefjp C++日本語リファレンス より引用．

unordered_set は、同一キーの要素を複数格納できず、格納順が規定されていないコンテナである。

コンテナ内の各要素は、キーのハッシュ値に基づきハッシュテーブルに格納されるため、決められた順序で並んでいるわけではない。

  • set は二分探索木で実装されているが，unordered_set はハッシュ値に基づくため，要素の順が規定されていない
  • vector からもイテレータを指定することで unordered_set に変換可能
  • 格納順が異なっても格納内容が一致すれば各コンテナの比較 == で true となる（逆に格納内容が一致しなければ false）
  • .count(Key) で指定した要素の個数（重複を許さないので 0 or 1）を取得可能
  • .insert(Value) で要素追加できる
    • 既に同じ要素が存在する場合は insert(Value).second で戻り値(bool)が false となる
  • erase(Key)，.clear() なども vector 同様に使える
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    unordered_set<string> uos_colors = {"orange", "pink", "red", "green", "blue", "red"};
    cout << uos_colors.size() << endl;
    for (auto itr = uos_colors.begin(); itr != uos_colors.end(); itr++)
    {
        cout << *itr << endl;
    }
    //output
    // 5
    // blue
    // green
    // red
    // pink
    // orange

    set<string> s_colors = {"orange", "pink", "red", "green", "blue", "red"};
    cout << s_colors.size() << endl;
    for (auto itr = s_colors.begin(); itr != s_colors.end(); itr++)
    {
        cout << *itr << endl;
    }
    //output
    // 5
    // blue
    // green
    // orange
    // pink
    // red

    vector<string> v_colors = {"orange", "pink", "red", "green", "blue", "red"};
    unordered_set<string> from_vector (v_colors.begin(), v_colors.end());
    cout << from_vector.size() << endl;
    for (auto itr = from_vector.begin(); itr != from_vector.end(); itr++)
    {
        cout << *itr << endl;
    }
    //output
    // 5
    // blue
    // green
    // red
    // pink
    // orange


    unordered_set<string> uos_colors2 = {"red", "orange", "blue", "blue", "green", "pink"};
    cout << "--" << endl;
    for (auto itr = uos_colors2.begin(); itr != uos_colors2.end(); itr++)
    {
        cout << *itr << endl;
    }
    //output
    // pink
    // green
    // blue
    // orange
    // red
    unordered_set<string> uos_colors3 = {"red", "orange", "green", "pink"};
    cout << "--" << endl;
    for (auto itr = uos_colors3.begin(); itr != uos_colors3.end(); itr++)
    {
        cout << *itr << endl;
    }
    //output
    // green
    // orange
    // pink
    // red

    cout << boolalpha << (uos_colors == uos_colors2) << endl;
    cout << boolalpha << (uos_colors == uos_colors3) << endl;
    //output
    // true
    // false

    cout << uos_colors.count("red") << endl;
    cout << uos_colors.count("white") << endl;
    //output
    // 1
    // 0

    uos_colors.insert("gray");
    cout << "--" << endl;
    for (auto itr = uos_colors.begin(); itr != uos_colors.end(); itr++)
    {
        cout << *itr << endl;
    }
    //output
    // gray
    // blue
    // green
    // red
    // pink
    // orange

    uos_colors.erase("gray");
    cout << "--" << endl;
    for (auto itr = uos_colors.begin(); itr != uos_colors.end(); itr++)
    {
        cout << *itr << endl;
    }
    //output
    // blue
    // green
    // red
    // pink
    // orange

    uos_colors.clear();
    cout << uos_colors.size() << endl;
    //output
    // 0

    return 0;
}

05 algorithm

ほとんど知らなかった項目なので，今後自分が使いそうな項目のみメモ．

  • 3つ以上の数値の最大値・最小値はリスト{...} を使って min({...}) のように書ける
  • min_element(itrFirst, itrLast) で配列の最小値のイテレータを取得でき，*をつけるとその値を取得できる
  • distance(itrFirst, min_element()) で最小値の位置を取得できる
  • minmax(変数 or リスト) で与えられた値の最小値，最大値の pair を取得でき，最小値は pair.first, 最大値は pair.second で取得できる
  • fill(itrFirst, itrLast, value) で配列を value で埋める
  • remove(itrFirst, itrLast, value) で配列中から value を削除して，削除した要素を埋めて並び直し（削除して余った領域は無効領域として残る），有効範囲のイテレータを返す
  • 上記の無効領域を削除するのが .erase で，.erase(remove(), itr.Last) で削除
    • remove と erase の説明はもとの書籍の図がわかりやすい こちら
    • 文字列に関しても上記で同様に削除できる（文字列が格納されている配列に対して value を文字列で指定）
  • remove_if(itrFirst, itrLast, unaryPred) で上記の条件付き削除が可能
    • unaryPred : []<Type>(return 条件) （例：{ return (n % 2 == 0); }）
  • reverse(itrFirst, itrLast) で要素を逆順にする
  • rotate(itrFirst, itrMId, itrLast) で，itrMid で指定した要素が先頭で itrLast まで続き，そのあとから残りの要素が itrFirst 続くように並び替える
  • unique(itrFirst, itrLast) で隣り合った要素が同じにならないように要素を削除して，削除した要素を埋めて並び直し（削除して余った領域は remove 同様無効領域とする），有効範囲のイテレータを返す
  • remove と同様，unique で返ってきたイテレータを erase(unique(), itr.Last) とすることで，無効領域を削除できる
    • sort 後，unique → erase とすれば重複要素の削除ができる（setでもできるが）
  • sort(itrFirst, itrLast, greater<>{}) で要素が大きい順に並べる（指定しない場合は小さい順）
  • nth_element(itrFirst, itrNth, itrLast) で，itrNth 番目の要素の値が，配列全体のうち N 番目に小さい値となるようにソートする（ただし，itrNth の前後は順不定）
  • lower_bound(itrFirst, itrLast, value) でソート済みの配列に対して value を挿入しようとする際，ソート状態を維持できかつ最も左の位置を取得し，その位置を示すイテレータを返す
  • 実際に何番目となるかは distance(itrFirst, lowe_bound()) で取得
  • lower_bound は最も左となる位置だが，upper_bound は最も右側となる位置
  • equal_range(itrFirst, itrLast, value) で lower_bound と upper_bound 両方の結果を pair で取得できる
  • ソート済みの2つの配列について，
    • 和集合（少なくともどちらか1つの配列に存在する要素集合）は set_union(itrFirst1, itrLast1, itrFirst2, itrLast2, itrOut) で取得可能
    • 積集合（両方の配列に存在する要素集合）は set_intersection(itrFirst1, itrLast1, itrFirst2, itrLast2, itrOut) で取得可能
    • 差集合（前者の集合から後者に存在する要素を取り除いた集合） は set_difference(itrFirst1, itrLast1, itrFirst2, itrLast2, itrOut) で取得可能
    • 対称差集合（2つの配列のどちらかにしか存在しない要素集合）は set_symmetric_difference(itrFirst1, itrLast1, itrFirst2, itrLast2, itrOut) で取得可能
    • 和集合のように重複した要素を削除することなく，マージした集合を得るのは merge(itrFirst1, itrLast1, itrFirst2, itrLast2, itrOut) で取得可能
      • いずれの場合も計算結果を itrOut で示したイテレータに格納できる（例：空の配列に back_inserter(配列名) で格納できる）
  • next_permutation(itrFirst, itrLast) で辞書順に次の順列を取得できる 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    cout << "--" << endl;
    int a = 30, b = 40, c = 10;
    cout << min({a, b, c}) << endl;
    //output
    // 10

    cout << "--" << endl;
    vector<int> data = {100, -3, 0, 10, 40, 1};
    cout << *min_element(data.begin(), data.end()) << endl;
    cout << distance(data.begin(), min_element(data.begin(), data.end())) << endl;
    //output
    // -3
    // 1

    cout << "--" << endl;
    auto p = minmax({a, b, c});
    cout << p.first << " " << p.second << endl;
    //output
    // 10 40

    cout << "--" << endl;
    fill(data.begin(), data.end(), 0);
    for (size_t i = 0; i < data.size(); i++)
    {
        cout << data[i] << endl;
    }
    //output
    // 0
    // 0
    // 0
    // 0
    // 0
    // 0

    cout << "--" << endl;
    data = {100, -3, 0, 10, 40, 1};
    auto itrRemove = remove(data.begin(), data.end(), 0);
    data.erase(itrRemove, data.end());
    for (size_t i = 0; i < data.size(); i++)
    {
        cout << data[i] << endl;
    }
    //output
    // 100
    // -3
    // 10
    // 40
    // 1

    cout << "--" << endl;
    auto itrRemove2 = remove_if(data.begin(), data.end(), [](int n){return (n%2==0);});
    data.erase(itrRemove2, data.end());
    for (size_t i = 0; i < data.size(); i++)
    {
        cout << data[i] << endl;
    }
    //output
    // -3
    // 1


    cout << "--" << endl;
    data = {100, -3, 0, 10, 40, 1};
    reverse(data.begin(), data.end());
    for (size_t i = 0; i < data.size(); i++)
    {
        cout << data[i] << endl;
    }
    //output
    // 1
    // 40
    // 10
    // 0
    // -3
    // 100


    cout << "--" << endl;
    data = {100, -3, 0, 10, 40, 1};
    rotate(data.begin(), data.begin() + 2, data.end());
    for (size_t i = 0; i < data.size(); i++)
    {
        cout << data[i] << endl;
    }
    //output
    // 0
    // 10
    // 40
    // 1
    // 100
    // -3

    cout << "--" << endl;
    data = {1, 1, 0, 10, 10, 3, 4, 5, 5};
    auto itrUnique = unique(data.begin(), data.end());
    data.erase(itrUnique, data.end());
    for (size_t i = 0; i < data.size(); i++)
    {
        cout << data[i] << endl;
    }
    //output
    // 1
    // 0
    // 10
    // 3
    // 4
    // 5

    cout << "--" << endl;
    sort(data.begin(), data.end(), greater<>{});
    for (size_t i = 0; i < data.size(); i++)
    {
        cout << data[i] << endl;
    }
    //output
    // 10
    // 5
    // 4
    // 3
    // 1
    // 0


    cout << "--" << endl;
    data = {100, -3, 0, 10, 40, 1};
    nth_element(data.begin(), data.begin()+2, data.end());
    cout << data[2] << endl;
    //output
    // 1


    cout << "--" << endl;
    data = {100, -3, 0, 10, 40, 1};
    sort(data.begin(), data.end());
    for (size_t i = 0; i < data.size(); i++)
    {
        cout << data[i] << endl;
    }
    //output
    // -3
    // 0
    // 1
    // 10
    // 40
    // 100
    cout << "--" << endl;
    auto itr = lower_bound(data.begin(), data.end(), -1);
    cout << *itr << endl;
    cout << distance(data.begin(), itr) << endl;
    //output
    // 0
    // 1

    cout << "--" << endl;
    itr = lower_bound(data.begin(), data.end(), 0);
    cout << *itr << endl;
    cout << distance(data.begin(), itr) << endl;
    //output
    // 0
    // 1

    cout << "--" << endl;
    itr = upper_bound(data.begin(), data.end(), 0);
    cout << *itr << endl;
    cout << distance(data.begin(), itr) << endl;
    //output
    // 1
    // 2

    cout << "--" << endl;
    auto itr_equal = equal_range(data.begin(), data.end(), 0);
    cout << *itr_equal.first << endl;
    cout << distance(data.begin(), itr_equal.first) << endl;
    cout << *itr_equal.second << endl;
    cout << distance(data.begin(), itr_equal.second) << endl;
    //output
    // 0
    // 1
    // 1
    // 2

    cout << "--" << endl;
    vector<int> vec1 = {0, 2, 5, 9};
    vector<int> vec2 = {2, 3, 4, 5};
    vector<int> vec3;
    set_union(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), back_inserter(vec3));
    for (size_t i = 0; i < vec3.size(); i++)
    {
        cout << vec3[i] << endl;
    }
    //output
    // 0
    // 2
    // 3
    // 4
    // 5
    // 9

    vec3.clear();

    cout << "--" << endl;
    set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), back_inserter(vec3));
    for (size_t i = 0; i < vec3.size(); i++)
    {
        cout << vec3[i] << endl;
    }
    //output
    // 2
    // 5


    vec3.clear();

    cout << "--" << endl;
    set_difference(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), back_inserter(vec3));
    for (size_t i = 0; i < vec3.size(); i++)
    {
        cout << vec3[i] << endl;
    }
    //output
    // 0
    // 9

    vec3.clear();

    cout << "--" << endl;
    set_symmetric_difference(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), back_inserter(vec3));
    for (size_t i = 0; i < vec3.size(); i++)
    {
        cout << vec3[i] << endl;
    }
    //output
    // 0
    // 3
    // 4
    // 9


    vec3.clear();

    cout << "--" << endl;
    merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), back_inserter(vec3));
    for (size_t i = 0; i < vec3.size(); i++)
    {
        cout << vec3[i] << endl;
    }
    //output
    // 0
    // 2
    // 2
    // 3
    // 4
    // 5
    // 5
    // 9


    cout << "--" << endl;
    data = {1, 2, 3, 4};
    do
    {
        for (size_t i = 0; i < data.size(); i++)
        {
            cout << data[i] << " ";
        }
        cout << endl;
    } while (next_permutation(data.begin(), data.end()));
    //output
    // 1 2 3 4
    // 1 2 4 3
    // 1 3 2 4
    // 1 3 4 2
    // 1 4 2 3
    // 1 4 3 2
    // 2 1 3 4
    // 2 1 4 3
    // 2 3 1 4
    // 2 3 4 1
    // 2 4 1 3
    // 2 4 3 1
    // 3 1 2 4
    // 3 1 4 2
    // 3 2 1 4
    // 3 2 4 1
    // 3 4 1 2
    // 3 4 2 1
    // 4 1 2 3
    // 4 1 3 2
    // 4 2 1 3
    // 4 2 3 1
    // 4 3 1 2
    // 4 3 2 1


    return 0;
}

06 tuple

省略

07 ios, iomanip

省略

数値誤差

C++ 競技プログラミング

atcoder.jp

を解いていての学び．

参考

drken1215.hatenablog.com

数値誤差

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    double a= 2.51;
    cout << (int) (a*100) << endl;

    return 0;
}

250

のように整数型にキャストした際に誤差が発生する可能性がある．上記の問題では入力 B を100倍して整数に変換し，整数同士の掛け算・割り算で解くことで AC できる．その100倍の方法は以下の2通り．

  1. 微小な値を加えて誤差回避
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    double b = 2.51;
    cout << (int) (b*100 + 0.0005) << endl;

    return 0;
}
  1. String 型で入力を受け取って変換
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    string s = "2.51";
    int b = (s[0] - '0') * 100 + (s[2] - '0') * 10 + (s[3] - '0');
    cout << b << endl;

    return 0;
}

最終的な AC コード

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    ll a;
    string b;
    cin >> a >> b;
    ll ib = (b[0] - '0') * 100 + (b[2] - '0') * 10 + (b[3] - '0');

    ll ab = a*ib / 100;

    cout << ab << endl;

    return 0;
}

範囲for文

C++

範囲for文というループの書き方を知らなかったのでメモ．

参考

上記サイトからの引用

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

int main() {
  vector<int> a = {1, 3, 2, 5};
  for (int x : a) {
    cout << x << endl;
  }
}

1
3
2
5

範囲for文はコンテナと呼ばれるデータ型に対して使うことができます。

std::map で要素のカウント

C++ 競技プログラミング

atcoder.jp

を解いてて他の方のコードを見ていて知ったのでメモ．

この問題は最初に各文字で始まる文字列を数えておくと良いが，自分の実装では

#include <bits/stdc++.h>

using namespace std;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    int count[5] = {0};

    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        if (s[0] == 'M')
        {
            count[0] += 1;
        }
        else if (s[0] == 'A')
        {
            count[1] += 1;
        }
        else if (s[0] == 'R')
        {
            count[2] += 1;
        }
        else if (s[0] == 'C')
        {
            count[3] += 1;
        }
        else if (s[0] == 'H')
        {
            count[4] += 1;
        }
        else
        {
            continue;
        }
    }

    for (int i = 0; i < n; i++)
    {
        cout << count[i] << endl;
    }

    return 0;
}

と愚直に書いていた．他の方のコードを参考にすると，std::map で書けるらしいと知ったので自分でも書いてみた．

#include <bits/stdc++.h>

using namespace std;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    map<char, int> count;
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        count[s[0]]++;
    }

    string s = "MARCH";
    for (int i = 0; i < n; i++)
    {
        cout << count[s[i]] << endl;
    }


    return 0;
}

std::map は平衡二分探索木で実装されているらしい．

std::set の要素参照

C++

std::set は二分探索木での実装なので operator[] でアクセスできない．イテレータを使う．

#include <bits/stdc++.h>

using namespace std;

int main(){
    set<int> st{3, 1, 4};
    
    for (auto itr = st.begin(); itr != st.end(); ++itr)
    {
        cout << *itr << endl;  
    }
    
    return 0;
}

1
3
4

std::set

C++ 競技プログラミング

atcoder.jp

簡単な問題だけど std::set を初めて使ったのでメモ．

#include <bits/stdc++.h>

using namespace std;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    set<int> s;
    for (int i = 0; i < 3; i++)
    {
        int x;
        cin >> x;
        s.insert(x);
    }
    if(s.size() == 2)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }



    return 0;
}

std::set は二分探索木として実装されるらしい．set はキーとデータが等しく，map はキーとデータが異なる．

std::set のリファレンス

set - cpprefjp C++日本語リファレンス