競技プログラミングで役立つC++の便利テクニック集

競技プログラミングでは、いかに素早く正確なコードを書けるかが成績を左右します。本記事では、実装時間の短縮やコードの高速化につながる、C++の実用的なテクニックを厳選して紹介します。コンテスト本番はもちろん、日常的なコーディングでも役立つ内容ばかりです。ひとつずつ見ていきましょう。

%演算子を使わずに奇数・偶数を判定する

数値が奇数か偶数かを判定する最もシンプルな方法が、ビット演算AND（&）を使う方法です。数値と1とのANDを取った結果が0でなければ奇数、0なら偶数と判断できます。仕組みは単純で、すべての奇数は最下位ビット（LSb）が1になっています。1とのAND演算によりLSb以外のビットがマスクされるため、結果を簡単に得られます。

if ((n & 1) != 0) {
    // 奇数
} else {
    // 偶数
}

シフト演算子による高速な乗算・除算

数値を2ⁿ倍したい場合は、左にnビットシフトするだけで計算できます。同様に、2ⁿで割りたい場合は右にnビットシフトします。乗算・除算命令よりも高速に動作するため、処理速度が求められる場面で有効です。

x = 40;
y = x << 2; // xを4倍 → y = 160
cout << y;

x = 40;
y = x >> 2; // xを4で割る → y = 10
cout << y;

XOR演算で2つの変数を入れ替える

一時変数を使わずに2つの数値を入れ替えるテクニックです。加減算でも実現できますが、ビットXOR（^）を使えばさらに簡潔に書けます。動作は手計算で確認してみてください。

// xとyを入れ替える
x ^= y;
y ^= x;
x ^= y;

strlen()なしで文字列を走査する

「strlen()関数を使用してはいけない」という制約が出題されることがあります。その場合も、文字列の先頭から順にアクセスするだけであれば自作のstrlen()は不要です。i番目の文字が有効（非ゼロ）である限り走査を続け、終端文字に到達したら停止すればよいのです。

for (int i = 0; s[i]; i++) {
    cout << s[i];
}

emplace_back()で高速化する

STLのvectorなどに要素を追加するとき、多くの人はpush_back()を使いますが、emplace_back()の方が高速です。push_back()が別の場所にオブジェクトを作成してからコピー（移動）するのに対し、emplace_back()はコンテナ内のメモリ上で直接オブジェクトを構築するため、余分なコピーが発生しません。

組み込みのGCD関数を使う

GCC環境では、最大公約数（GCD）を求める組み込み関数__gcd()が利用できます。

__gcd(x, y) // xとyのGCDを求める

なお、C++17以降では標準ライブラリのstd::gcd()（<numeric>ヘッダ）も使えるので、移植性を重視する場合はこちらを選ぶとよいでしょう。

配列サイズの上限に注意する

main関数内（ローカル変数）で宣言できる配列のサイズはおよそ10⁶程度が上限です。一方、グローバル領域に宣言すれば10⁷程度まで確保できます。大きな配列が必要な場合は、グローバル宣言を検討しましょう。

log10()で最上位桁を求める

対数演算を使うと、任意の整数の最上位桁（一番左の桁）を直接求められます。

n = 4578;
double k = log10(n);
k = k - floor(k);
int x = pow(10, k); // x は最上位桁（4）

log10()で桁数を直接計算する

ループで数えなくても、対数を使えば桁数を一発で求められます。

n = 4578;
int digit_count = floor(log10(n)) + 1;

2のべき乗かどうかを判定する

次のビット演算の論理式を使えば、数値が2のべき乗かどうかを即座に判定できます。2のべき乗は2進表現でビットが1つだけ立っているという性質を利用しています。

x = 1024;
bool check = x && (!(x & (x - 1))); // trueなら2のべき乗

all_of / any_of / none_of で条件を一括チェック

C++には、範囲内の要素が条件を満たすかどうかをまとめて判定できるアルゴリズムが用意されています。

all_of(left, left + n, isPositive());  // すべて正かどうか
any_of(left, left + n, isPositive());  // 少なくとも1つ正かどうか
none_of(left, left + n, isPositive()); // 正の要素が1つもないかどうか

copy_n()で要素をコピーする

あるコンテナから別のコンテナへ要素をコピーするには、copy_n()が便利です。

int src[5] = {10, 20, 30, 40, 50};
int des[5];
copy_n(src, 5, des);

iota()で連続する値を生成する

iota()を使うと、指定した初期値から始まる連続的に増加する数列を範囲に代入できます。*firstに初期値を代入した後、後置インクリメントで値を更新していくイメージです。

int arr[5] = {0};
char str[5] = {0};
iota(arr, arr + 5, 15);   // {15, 16, 17, 18, 19} を生成
iota(str, str + 5, 'A');  // {'A', 'B', 'C', 'D', 'E'} を生成

2進数リテラルで値を代入する

接頭辞0bを付けると、数値を2進数で直接記述できます。ビットフラグなどを扱う際に可読性が大きく向上します。

int x = 0b1101; // x は 13 になる

and や or などのキーワードを使う

C++では、条件演算子の代わりにキーワード形式の代替表現を使えます。たとえば「and」は「&&」、「or」は「||」の代わりに使用できます。

x = 10;
if (x < 10 and x > 5)
    cout << "True" << endl;
else
    cout << "False" << endl;
// True と出力される

これらのテクニックは単なる小技にとどまらず、実装スピードとコード品質の両方を高めてくれるものばかりです。ぜひ練習問題やコンテストで実際に使いながら身につけてください。