はじめに

前回、AtCoderの基本的な知識とともにAtCoderで最も使われている言語c++を学ぶため、C++入門 AtCoder Programming Guide for beginners(APG4b)の第2章まで取り組んでみた。
今回は、残りの第3章「競技プログラミングに役立つ知識」と第4章「今まで説明していなかったこと」に取り組む。
ちなみに、普段はswiftを使っている人間から見たコメントになってます。swift嫌いの人はゴメンね。

AGP4bで学ぶAtCoder知識（後編：第3章〜）

(前回からの続きになる。)

Y - 3.01.数値型では、int(範囲:-2^31 〜 2^31-1),double(桁数上限約16桁),int64_t(範囲:-2^63 〜 2^63-1)について、詳しく説明されている。つまり、AtCoderでは、この3つの型さえ覚えておけば十分と言うことだろう。
AP1 - 付録1.コードテストの使い方は重要。僕の場合は、コンテスト中はpaiza.ioでコードを書いて動作確認して、できあがったら、AtCoder謹製のコードテストで最終確認してから提出している。paiza.ioとコードテストのc++のバージョンが違ってたらエラーになるかも知れないし、paiza.ioではタイムアウトにならなくても、コードテストではアウトになるかも知れないしね。
AP4 - 付録4.ループの裏技repマクロも重要かな。少しでもコードを書く量を減らすためには重要なテクニック。ていうか、c++のfor文の書式は美しくないよね。swiftのfor文はシンプルだから、こんなテクニックを使うまでもないんだよね。

AGP4bにおけるc++の豆知識（後編：第3章〜）

(前回からの続きになる。)

Y - 3.01.数値型では、double型をcoutに出力するときの桁表示の設定コマンドsetprecisionとfixedが紹介されていた。使い方は言葉で示すより、コードで示した方が分かり易いと思う。

    cout << 0.00123456789 << endl; // 0.00123457
    cout << 1.23456789 << endl; // 1.23457
    cout << 12345.6789 << endl; // 12345.7
    
    cout << setprecision(4) ;
    cout << 0.00123456789 << endl; // 0.001235
    cout << 1.23456789 << endl; // 1.235
    cout << 12345.6789 << endl; // 1.235e+04
    
    cout << fixed << setprecision(4) ;    
    cout << 1.23456789 << endl; // 1.2346

setprecision単体だと、有効桁数を設定でき、fixedと組み合わせると、小数点以下の桁数を設定できる。なお、何も指定しないとき、coutは有効桁数6桁となっている模様。また、元の数字を「四捨五入」して丸めている。
また、setprecisionはint型には影響しないこと、キャストは、(型名)で行えることが説明されている。int型へのキャストは小数点以下切り捨てであることに注意。

  cout << fixed << setprecision(5);
 
  int a = 5;
  cout << a << endl; // 5 :int型の出力
  cout << (double)a << endl; // 5.00000 :double型の出力
  
  double b = 4.56789;
  cout << b << endl; // 4.56789 :double型の出力
  cout << (int)b << endl; // 4 :int型の出力

ちなみに、このY - 3.01.数値型で、「printf」「scanf」「to_string」「c_str」「stoi(stoll,stod)」「size_t」の説明も書かれている。どれも重要なので、一つでも分からない言葉があれば、ここで潰しておいた方が良い。
Z - 3.02.pair／tupleとautoで、タプルの使い方が書かれていた。tuple<型名1, 型名2, ...>とかmake_tapleなんてイニシャライザがあるのか...。swiftに慣れた身からすると、わざわざ、コマンドがあることに違和感ありまくり。swiftでは、var a = (123,"abc")って感じで書けちゃうからね。まぁ、c++のタプルは使う場面になったときに覚えれば良いかな。あーもー、めんどうくせぇなぁ。swiftからみると、古くさ過ぎるわ。要らない要素にアクセするときにignoreを使うとか、swiftなら_で済むのに〜。

//初期化①
tuple<int, string ,double> data(1, "abc",9);
//アクセス①
cout << get<2>(data) << endl;  //<>の添字は変数iを使えず、実数のみ

//初期化②
tuple<int,int> tpl;
tpl = make_tuple(10,20);
//アクセス②
int b;
tie(ignore,b) = tpl;// ignoreは使わない要素に使う。
cout << b << endl; // 20

autoがタプルと同じ節で説明されるのは変な感じだ。まぁ。autoなんてarduinoでも使われまくってる基本事項だし、説明不要よね。単に、後付けでコンパイラによって型付け（＝型推論）させるよ、という宣言。swiftでは、変数の宣言時に型を明記しなければ、自動的にauto宣言したのと同じになってるしね。
この節では、using 新しい型名 = 型名;という型エイリアスも説明されている。節の名称からは想像つかないよね。ちなみに、typedefも同じ機能があるけど、usingを使うべきだってさ。

  typedef pair<int, int> pii;  // pair<int, int> に pii という別名を付ける
  pii p = make_pair(1, 2);
  cout << "(" << p.first << ", " << p.second << ")" << endl;

ジャパニーズ英語の使い手としては、typedefの方が記憶に残りやすそうなコマンドだけどね。
こんな使い方も示されていた。

using vi = vector<int>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

int N = 10, M = 20;
vvi data(N, vi(M));  // N * M の2次元配列

ちなみに、このdataって、単なる変数名なんだよね。紛らわしいよね。初心者向けにコマンド名と単なる変数名は区別付くようにして欲しいわ。この配列dataを調べると、全ての要素が0で初期化されてるね。当然だけど、10x20の配列の範囲を超える要素を参照しようとするとエラーとなる。まぁ、当然だね。

cout << data[1][1] << endl; // 0
data = { // 2x3の配列範囲だけ上書き
    {1,2,3},
    {2,3,4}
};
cout << data[1][1] << endl; // 3 - 上書き後の値
//   cout << data[10][20] << endl; // Segmentation fault (core dumped)

この節の練習問題であるEX22 - 2つ目の値でソートでは、2要素タプルの配列について、第2要素の昇順で並び替えさせる問題だけど、sortコマンドを使って並べ替えさえさせている。タプルをsortコマンドで並び替えさせるときは、第1要素＞第2要素＞･･･の優先順位で並び替えを行うけど、模範解答では、第2要素と第1要素を入れ替えたタプルを使って並び替えさせている。まぁ、それも良いけど、swiftでは、並び替えの条件を簡単に設定できるから、模範解答の回避策にはガックリきたけど、少し調べたら、後ろの方で、sortコマンドに第3引数として、比較関数を設定する方法が書いてあった。sortコマンドに第3引数を設定して解答するとこんな感じ。

#include <bits/stdc++.h>
using namespace std;
 
using pii = pair<int,int>;
using vp = vector<pii>;
 
int main() {

    int n = 0;
    cin >> n;
    vp ps;
    for (auto i=0;i<n;i++){
        int p1,p2;
        cin >> p1 >> p2;
        ps.push_back(pii(p1,p2));
    }

    auto comp = [](pii a, pii b) { return a.second < b.second; };

    sort(ps.begin(),ps.end(),comp);

    for (auto i=0;i<n;i++){
        cout << ps[i].first << " " << ps[i].second << endl;
    }

}

うーむ。比較関数compをつくるイニシャライザの頭に付いてる[]が意味わからんね。だから、この節では、比較関数の解説を飛ばしたのか。ちなみに、[]を使った構文は、c++におけるラムダ式の記法とのこと。auto 関数名 = [](引数の型1 引数名1, 引数の型2, 引数名2, ...) { 関数の処理 };のように書く。swift風に言えば、クロージャだね。でも、ラムダ式と言われてしまうと、何年か前に読んだこの本のHaskellを思い出すね。もう、殆ど内容を覚えてないけど、今から読み返したら昔よりは理解が深まるかな？
AA - 3.03.STLのコンテナでは、配列もどき（map,queue,set）が色々と紹介されている。c++のmapはswiftのDictionary型なのね。mapと言われると、map関数を連想しちゃうから紛らわしいね。それに、mapのkeyとvalueにアクセスするときは、pairと同様に.firstと.secondなのよね。c++のセンスのなさに泣ける。
APG4bでは、コンテナを用いた処理での計算量が示されているのが良いね。下記はmapの例。
上記で、mapの値へのアクセスはO(logN)になっているけど、配列vectorの場合はO(1)であることに留意。まぁ、keyとの比較処理を伴わないvectorの方が計算量が少ないのは感覚的に分かると思うけどね。
最大の要素の取得計算量がO(1)となるpriority_queueというコンテナも存在しる。swiftでは見た記憶ないから、面白いね。今いち、使い道が分からんけどね。
また、おもしろいコンテナとして、unordered_mapも紹介されてて、これを用いた処理の計算量は下記の通り。平均O(1)と書いてあるとおり、コンテナの要素数Nに比例しないけど、計算量O(logN)のmapより早いとは限らないことに注意。まあ、Nが十分大きいときは、unordered_mapの方が早く処理が終わるんだろうけどね。
また、昇順化した配列の閾値以上/以下の最小値/最大値を求めるlower_bound / upper_boundも紹介されている。

  auto a = {0, 10, 13, 14, 20};
  // aにおいて、12 以上最小の要素は 13
  cout << *lower_bound(a.begin(), a.end(), 12) << endl; // 13

関数名の頭に「*」を付ける記法は、後の章で説明されるけど、ポインタ(メモリアドレス)という言葉を知ってる人向けに端的に説明すれば、ポインタ変数pにたいして、pに格納されている値を*pで取り出すのがc++の流儀、と言うこと。ちなみに、intの値を格納するポインタ変数を定義するときの書式がint* pなんだよね。ちょっと、こんがらがるよね。
AB - 3.04.構造体では、構造体の説明がされている。swiftと違って、イニシャライズ時はメンバの名称は無視して、メンバの順番のみで値を入れる流儀の模様。でも、値取得の時はメンバ名を使うのは一貫性ないよね。一貫性の低いルールは暗記力低い人には馴染めないね。

struct MyPair {
  int x;     // 1つ目のデータはint型であり、xという名前でアクセスできる
  string y;  // 2つ目のデータはstring型であり、yという名前でアクセスできる
};
 
int main() {
  MyPair p = {12345, "hello"};  // MyPair型の値を宣言
  cout << "p.x = " << p.x << endl;
  cout << "p.y = " << p.y << endl;
}

swiftのコンストラクタinit()に相当するのが、構造体名()の模様。

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

struct NumString {
  int length;
  string s;
  // コンストラクタ
  NumString(int num) {
    cout << "constructor called" << endl;

    // 引数のnumを文字列化したものをsに代入し、sの文字数をlengthに代入する
    s = to_string(num);  // (STLの関数)
    length = s.size();
  }
};

int main() {
  NumString num(12345);  // コンストラクタに 12345 が渡される
  cout << "num.s = " << num.s << endl;
  cout << "num.length = " << num.length << endl;
}

この辺の感覚はswiftに似てるね。
また、2項演算子を自作の構造体に使うためにオーバーロードするコマンドoperatorも紹介されている。下記は「＋」演算子のオーバーロード例。

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

struct MyPair {
  int x;
  string y;
  // 別のMyPair型のオブジェクトをとって、x, yにそれぞれ+したものを返す
  // +演算子をオーバーロード
  MyPair operator+(const MyPair &other) {
    MyPair ret;
    ret.x = x + other.x;  // ここではint型の+演算子が呼ばれる
    ret.y = y + other.y;  // ここではstring型の+演算子が呼ばれる
    return ret;
  }
};

int main() {
  MyPair a = {123, "hello"};
  MyPair b = {456, "world"};

  // MyPair型の+演算子が呼ばれる
  MyPair c = a + b;

  cout << "c.x = " << c.x << endl;
  cout << "c.y = " << c.y << endl;
}

新登場のconstは、swiftでいうところのlet（定数宣言）だね。
練習問題のEX24 - 時計の実装は、c++の構造体の使い方を確認する意味ではやった方がいいね。でも、この段階では、書式設定した文字列格納コマンドsnprintf()を使わない前提だから、0-9の数値を2桁化するため、if文で10未満を確認して、頭に"0"を追加する面倒なことをしている。snprintf()を使うより、こういう書き方の方が競プロっぽいのかな？
AC - 3.05.ビット演算では、競技プログラミングで多用するbit演算の解説がされる。
まあ、ビット演算はどの言語でもあるから、説明はいらんとおもうけど、表は載せておくね。
そして、c++のSTLには、bitsetという特殊な型があり、数値の2進数表示をsnprintf()やformat()を使わずに実現できて便利。

    bitset<4> a("0011");
    bitset<4> b(3);
    bitset<8> c;

    cout << a << endl; // 0011 
    cout << b << endl; // 0011
    cout << c << endl; // 00000000

また、bitsetは通常の数値と同様にbit演算子が使えるだけでなく、下記のようなメソッドが使える。

    cout << a.to_string() << endl; // 0011 ：文字列へ変換
    cout << b.to_ulong() << endl; // 3 ：unsigned long型へ変換
    
    cout << c.size() << endl; // 8
    cout << b.count() << endl; // 2
    cout << (a == b) << endl; // 1(ture)
    cout << (a != b) << endl; // 0(false)   
    cout << c.none() << endl; // 1(true)

また、下記のような操作もできる。
setやtestを使わずに、変数[位置]のようにアクセスすることもできる。

    bitset<4> a("0011");
    bitset<4> b(3);
    bitset<8> c;

    cout << a[0] << endl; // 1
    cout << a[1] << endl; // 1
    cout << a[2] << endl; // 0
    cout << a[3] << endl; // 0
    
    c.set(2,1);
    cout << c << endl; // 00000100
    cout << c.test(2) << endl; // 1 -- 2bit目のビット
    cout << c.test(3) << endl; // 0 -- 3bit目のビット
    
    b.reset(0);
    cout << b << endl; // 0010
    b.flip();
    cout << b << endl; // 1101

c++のbitsetは便利だけど、今まで存在も知らずにいたなぁ。じっさい、bitset使わなくても、普通の整数もint x = 0b100とかで二進数表記で代入できるし、cout << (x>>2 & 1) << endl;で2ビット目が立ってるかを調べることも出来るしね。bitsetで便利だなと思ったのは、立っているビットの総数が分かる.count()かなぁ。
AtCoderで頻出のbit全探索の例題も出ているから、bit全探索を知らない人は解いた方が良いよ。bit全探索を使うような組み合わせ問題で、bit全探索以外のコードを書こうとしたら、かなり大変だと思う。swift的に書くと、例えば、配列vs(0..<n)があったとして、合計値をmとする要素の組み合わせがあるか？という問題が、bit全探索の典型的な問題だけど、もし、bit全探索の手法を使わないと、n=5だとこんな書き方かな？

let (n,m) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
let vs = readLine()!.split(separator:" ").map{Int($0)!}

var ans = "No"

OUT:for i0 in 0...1 {
    for i1 in 0...1 {
        for i2 in 0...1{
            for i3 in 0...1{
                for i4 in 0...1{
                    if i0*vs[0] + i1*vs[1] + i2*vs[2] + i3*vs[3] + i4*vs[4] == m {
                        ans = "Yes"
                        break OUT
                    }
                }
            }
        }
    }
}

print(ans)

アホみたいに面倒でしょ？面倒だと思ったら、bit全探索のやり方を覚えた方が良いよ。というか、知らないと、AtCoderで時間内に解けない。そもそも、これ、n=5にしか対応してないや。n=10とかにもフレキシブルに対応しようとしたら、bit全探索以外に思いつかないね。
と思ったけど、bit全探索以外にも、nが5でも10でもフレキシブルに対応できる解法があった。下記は深さ優先探索(depth first search)と言うらしい。コードを理解しようとすると頭がこんがらがるね。この再帰関数を使う手法は、dp法で使うなら意味あるかもけど、全探索的に使う場合は、bit全探索の手法の方が分かりやすくていいね。

let (n,m) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
let vs = readLine()!.split(separator:" ").map{Int($0)!}

//f(i,sum)は、i番目以降の数値について、含める含めないが未定の状態で、
//合計額がsumであるときの判定式
func f(_ i:Int,_ sum:Int) -> Bool {
    if i == n {return sum == m} //残りの数値vs[i]が存在しないので、sum==mで判定
    
    if f(i+1 , sum) {return true} //i番目の数値vs[i]を足さない場合のi+1の判定式に従う
    if f(i+1 , sum + vs[i]) {return true} //i番目の数値vs[i]を足した場合のi+1の判定式に従う
    return false // i番目の数値を足しても足さなくても、i+1の判定式がfalseの場合
}

print(f(0,0) ? "Yes" : "No")

EX25 - 集合の操作は、bit演算子の再確認の意味でやった方が良いね。
AD - 3.06.その他の機能では、いろいろな細かい的ニック的なことが書かれているので、列挙していく。
文字(文字列ではなく、1文字)であるchar型の実体は数値であることを活用したプログラムの説明。
定数を定義するconst修飾子の使いどころとして、bitset<(定数)ビット数>のイニシャライズが上げられている。
三項演算子（○○ ? ×× : ▲▲）が示されているけど、今ここで？って気もするね。
論理演算の短絡評価が説明されている。つまり、論理演算子の&&と||は左の式から実行し、結果が確定した時点で条件判定処理を中断するということ。むかし、聴いた気がするな。
#define マクロ名(引数1, 引数2, ...) 置き換えるプログラムを使ったマクロが説明されている。競プロでよく使われるマクロとして、次の二つが紹介されている。

//rep 繰り返す処理のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
// 利用例
    rep(i, 5) cout << "abc" << endl; // 5行のabcを出力する


// all sort文の省略化
#define all(v) v.begin(), v.end()
// 利用例
  vector<int> v = { 2, 3, 1 };
  sort(all(v)); // 2回配列変数名を書く必要がない

ラムダ式の書式がauto 関数名 = [](引数の型1 引数名1, 引数の型2, 引数名2, ...) { 関数の処理 };と書かれている。まあ、swiftでクロージャと呼ばれているものと似てるから馴染みはあるけどね。面白いのは、()の引数の他、外部環境の変数を使って処理することが出来て、その場合は、先頭の[]を[&]とすることかな。

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

int main() {

  // 最大値を保持する変数
  int max_num = 0;

  // 今まで受け取った値の中から最も大きな値を返す関数
  auto update_max = [&](int n) {
    if (max_num < n) {
      max_num = n;
    }
    return max_num;
  };

  cout << update_max(5) << endl; // 5
  cout << update_max(2) << endl; // 5
  cout << update_max(10) << endl; // 10
  cout << update_max(4) << endl; // 10

  cout << max_num << endl; // 10
}

やっぱり、swiftとは微妙に違うな。swiftのクロージャだと、[&]みたいな特別な書式を使わなくても、外部環境の変数を使うことが出来る。

// 最大値を保持する変数
var max_num = 0

// 今まで受け取った値の中から最も大きな値を返す関数
let update_max = { (n:Int) -> Int in
    if (max_num < n) {
        max_num = n
    }
    return max_num
}

print(update_max(5)) // 5
print(update_max(2)) // 5
print(update_max(10)) // 10
print(update_max(4)) // 10
 
print(max_num) // 10

ラムダ式を使った再帰関数は、わざわざfunctionを型とする必要があると説明されているけど、これは、c++11の書き方で古い。c++23が最新形だけど、新しすぎてネットの情報が少ないだろうから、c++14/17/20で使われていた書き方を紹介する。
0〜nの整数を全て合計する再帰関数。本来、引数はnだけで良いところ、再帰関数であることを明示するため、selfが第1引数に入っている...あれ？新しい書き方のくせに、何かダサいぞ？

  // 再帰関数の定義
  auto sum = [](auto self,int n) -> int {
    if (n == 0) {
      return 0;
    }
    int s = self(self , n - 1);
    return s + n;
  };
 
  cout << sum(sum,3) << endl; // 6

c++11の書き方だと、functionの頭書きが意味不明だけど、それ以外はスッキリしてる。

  // 再帰関数の定義
  function<int(int)> sum = [&](int n) {
    if (n == 0) {
      return 0;
    }
    int s = sum(n - 1);
    return s + n;
  };
 
  cout << sum(3) << endl;

しつこいかも知れないけど、swiftの場合は....スッキリ!!!

let sum = {(n:Int)-> Int in
    if (n == 0) {
      return 0
    }
    return sum(n-1) + n
}
print(sum(3)) // 6

AF - 4.01.includeディレクティブでは、#include ...の解説をしてくれている。競技プログラミングには直接関係ないことでも、c++の知識としては重要だから解説してくれている。正直、競技プログラミングのHPに載せておくのがもったいないのでは？とおもうね。これ単体で、HPを開設しても良いくらいじゃないかな。売り物のc++の学習書なんかより、全然役立つしね。
AH - 4.03.テンプレートでは、テンプレートの解説がされている。関数テンプレートとクラステンプレートがあるけど、swiftで言うところのジェネリック関数とジェネリック型だね。

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

  int a = 3;
  double b = 1.2;
 
  cout << square<int>(a) << endl;  // int版のsquare関数の呼び出し
  cout << square<double>(b) << endl;  // double版のsquare関数の呼び出し

swiftなら...やっぱりスッキリ！！！c++と違うのは、ジェネリック型の定義時点で、型Ｔが乗算「*」が可能な型であることを条件付ける必要があることかな。Numericは乗算が可能なプロトコルだから、square関数を定義できた。where句を削除するとエラーになる。

func square<T>(_ x:T) -> T where T: Numeric {
  return x * x;
}
 
let a = 3;
let b = 1.2;
 
print(square(a))  // Int版のsquare関数の呼び出し
print(square(b))  // Double版のsquare関数の呼び出し

AI - 4.04.イテレータでは、イテレータの説明がされている。ぱっと見は、イテレータと、配列のindexの違いが分からないと思うけど、swiftで言うところの「Collection」と「配列」の違いを理解するのが分かり易いと思う。
Collectionも配列も要素の集合体であり、どちらの要素も添字（index）を持つ。しかし、Collectionの添字間に順番の要素はないのに対し、配列の添字は順番を持つ。これが大きな違いとなっている。とはいえ、Collectionの要素には先頭も終端もある。どゆこと？と思うかも知れないけど、各要素自体は、次の要素はどれか？を情報として持っている。つまり、一つ一つの要素に順番に後ろの要素を教えて？と聞き続ければ、先頭から終端まで、要素にアクセスできる。
言い換えれば、配列は、添字間の順番を予めどこかのメモリに保管しておいて、各要素に聞く手間を省いていると言える。配列は、要素に直接アクセスできて便利な気もするけど、全ての添字間の順番を別途メモリに保管するひつようがあるため、効率が悪い面もある。例えば、配列の要素の一つを削除したときは、添字間の順番を保管したメモリの内容も大幅に塗り替える必要がある。その点、Collectionの要素を一つ削除した場合は、削除した要素の一つ前の要素の「次の要素の位置」を塗り替えるだけで済む。
ここまでの説明で、想像が付いたと思うけど、イテレータというのは、swiftで言うところのCollectionの一つ一つの要素にアクセスするための手段だと分かる。swiftのCollectionは、c++のコンテナに相当すると言える。なお、swiftにおいて、配列がCollectionの一つであるのと同様に、c++においても配列はコンテナの一つなので、配列もイテレータが使える。
具体的なイテレータの使い方は、APG4bを直接読んで欲しい。
AJ - 4.05.ポインタは、c言語のキモだね。キモだけに、ここで書くような話ではないので、各自、しっかり読み込んでね。ただし、競技プログラミングで使わないテクニックだから、安心して。あれ？ここで4章終わっちゃった。

おわりに

とりあえず、競プロで必要なc++の書き方は一通り学んだと思うけど、やっぱり、swiftと比べて美しくないね。
他人のc++で書いたプログラムは読めるようになったと思うから、勉強した甲斐はあったと思うけど、自分が書くときは、やっぱりswiftかな。
そういえば、蟻本もc++で書いているのか。そういう意味では、c++は競技プログラミングにチャレンジする人間にとって、必修科目なんだな。
次は、蟻本を頑張るよ。