ちょっとしたコーディングテクニック

C++の仕様や便利機能に対し，こちらは言語を問わずに使えるコーディングテクニックを紹介する．

円状に並ぶ要素

同じ数列を$2$つ連結することで数列の先頭と末尾が繋がって処理しやすくなる

`vector`以外のデータ構造

queueやstack，dequeを用いると，vectorよりも簡潔に書けることがある．

幅優先探索(queue)
深さ優先探索(stack)
括弧列の検証(stack)
逆ポーランド記法(stack)
ヒストグラムの最大面積(stack)
01BFS(deque)

番兵，余分な要素

例外処理を完結にするために，番兵と呼ばれる特殊な値を配列の先頭や末尾に挿入しておく． C言語だと，文字列におけるナル文字\0がその例である．

大きな数を使う手法

問題を言い換えると，

$N$個の正の整数$a_1, a_2, \dots, a_N$が与えられる($0\leq a_i\leq 10^9$)．
$N$個の整数のうち，偶奇が同じ$2$つの数を取り出して和を考えるとき，その最大値を求めよ．
存在しない場合はその旨を出力せよ．

奇数と偶数で分けて，それぞれ大きい方から$2$つ和のうち大きい方を出力すれば良い．ただし，奇数が$1$つしかない場合や偶数が$1$つしかない場合を考慮する必要がある．このとき，奇数や偶数の配列に$-10^{12}$を$2$つずつ入れておくことで，答えがマイナスになった場合はそのような数が存在しないことを表すことができる(実装例)．

迷路を壁で囲む

グリッドで表される迷路を探索するような問題で，盤面を囲むような壁を設置することで，グリッドの端に到達したときの処理を簡潔にすることができる．

天井関数

int ceil(int a, int b) {
    return (a + b - 1) / b + 1;
}

を用いると，$a/b$以上の最大の整数を求めることができる． C言語では，ceil関数が標準ライブラリに含まれているが，浮動小数点の計算を信用していない人はこれを使うと良いだろう．

浮動小数点型を使わない

浮動小数点型を使わないことで，計算誤差を防ぐことができる．例えば，$\frac{a}{b}$と$\frac{c}{d}$の値の比較を行う場合，$a/b<c/d$という式を書かずに，$a\cdot d<c\cdot b$という式を書くことで，誤差を防ぐことができる(オーバーフローには注意)．

他にも，ルートがつかないように変形したり，logの真数の比較であったり，整数の範囲でできる場合はしたほうが良い．

グリッドの移動

グリッドで$(x,y)$から上下左右の移動をするとき，$(x+1,y),(x,y+1),(x-1,y),(x,y-1)$の処理を行うが，これを配列に格納しておくと，for文を用いて簡潔に書くことができる．

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
for (int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    // (nx, ny)に対する処理
}

これは$8$方向のときや，移動できる方向が制限されている場合にも応用できる．

超頂点

グラフの頂点に番号がふってあり，同じ番号同士であれば行き来できるようなグラフを考える．

shiba's Library