競技プログラミングで役立つC++の実践テクニック集（C++11対応）

はじめに

本記事では、競技プログラミングで役立つ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を掛けるので y = 160
cout << y;

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

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

+と-演算子でも実現できますが、ビットXOR演算子を使う方法もあります。手作業で確認すれば正しく動作することが分かります。

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

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

strlen()関数の使用が禁止されている場合でも、各位置の文字が有効（非ゼロ）であるかをチェックしながら走査できます。文字列はヌル文字で終端されているため、これで十分です。

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

5. push_back()の代わりにemplace_back()を使う

vectorなどのコンテナへ要素を追加する際、emplace_back()を使うとより高速です。この関数は別の場所にメモリを確保してからコピーするのではなく、コンテナ内で直接オブジェクトを構築するためです。

6. 組み込みのGCD関数を活用する

C++には最大公約数（GCD）を求める組み込み関数が用意されています。さまざまな場面で利用できます。

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

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

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

8. log演算で最上位桁を求める

対数演算を使えば、任意の数値の最上位桁を計算できます。

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

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

ループ処理を使わずに、桁数を一発で求められます。

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

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

次のロジックで、数値が2のべき乗かどうかを直接判定できます。

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

12. copy_nで要素をまとめてコピーする

copy_n関数を使うと、あるコンテナから別のコンテナへ要素を簡単にコピーできます。

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

13. 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'} を生成

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

数値の前に0bプレフィックスを付けると、その数値が2進数表記であることを示せます。

int x = 0b1101; // xには13が格納される

15. 代替キーワード（and / or など）を活用する

C++では、条件演算子の代わりに専用キーワードを使用できます。例えば「&&」の代わりに「and」と書けます。

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

まとめ

これらのテクニックは、ビット演算や標準ライブラリを上手く活用することで、コードをより短く、速く、読みやすくしてくれます。競技プログラミングの制限時間内で実装を完了させるために、ぜひ日頃から使いこなせるようにしておきましょう。