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

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;
}