競技プログラミング初心者が知っておくべきC++の便利テクニック15選

本記事では、競技プログラミングで活躍するC++の実用的なテクニックを多数紹介します。これらを覚えておくと、コードを書く時間を大幅に短縮でき、コンテスト中の貴重な時間を問題の考察に充てられるようになります。それでは、一つずつ見ていきましょう。

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

数値と1のビットANDを取るだけで判定できます。結果が0以外なら奇数、0なら偶数です。すべての奇数は最下位ビット（LSb）が1になっているため、AND演算で他のビットがマスクされ、簡単に判定できるという仕組みです。

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

2. シフト演算による高速な掛け算・割り算

2ⁿを掛けたい場合は左にn回シフト、2ⁿで割りたい場合は右にn回シフトするだけです。乗除算命令よりも高速に動作します。

x = 40;
y = x << 2; // x × 4 = 160
x = 40;
y = x >> 2; // x ÷ 4 = 10

3. 一時変数なしで2つの値を入れ替える

+と−演算子でも可能ですが、XOR演算子を使えばさらにスマートに書けます。

// xとyを交換
x ^= y;
y ^= x;
x ^= y;

4. strlen()を使わずに文字列を走査する

strlen()の使用が制限されている場合でも、i番目の文字が有効（非ゼロ）かどうかを確認しながらループすれば、文字列の終端まで安全に処理できます。

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

5. push_back()よりもemplace_back()を使う

vectorなどのコンテナに要素を追加するとき、emplace_back()の方が高速です。別の場所にメモリを確保してからコピーするのではなく、コンテナ内で直接構築するためです。

6. 組み込みのGCD関数を使う

C++には最大公約数を求める関数が用意されています。

__gcd(x, y) // xとyの最大公約数を求める

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

main関数内で宣言できる配列の最大サイズは約10⁶程度ですが、グローバル変数として宣言すれば10⁷程度まで確保できます。大きな配列が必要な場合はグローバル宣言を検討しましょう。

8. log10で最上位桁（先頭の数字）を求める

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

9. log10で桁数を直接計算する

ループを使わずに一発で桁数が求まります。

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

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

2のべき乗はビットパターン上「1が1つだけ立っている」数なので、次の式で判定できます。

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

11. 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()); // 正の要素がないかどうか

12. copy_nでコンテナ間のコピーを行う

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

13. iotaで連続する値の列を生成する

標準アルゴリズムのiota()を使うと、初期値から順に増加していく値の列を一括生成できます。

int arr[5] = {0};
iota(arr, arr + 5, 15);        // {15, 16, 17, 18, 19} を生成

14. 2進数リテラルで直接代入する

接頭辞「0b」を付ければ、数値を2進表記で記述できます。

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

15. 演算子の代わりにキーワードを使う

C++では「and」などのキーワードを演算子の代わりに使えます。可読性が上がる場面もあります。

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

これらのテクニックは単なる省力化にとどまらず、計算量の削減やバグの防止にもつながります。まずは実際に手を動かして試し、自分のコードスタイルに取り入れてみてください。