C++

競技プログラミングでは、いかに素早く正確なコードを書けるかが成績を左右します。本記事では、実装時間の短縮やコードの高速化につながる、C++の実用的なテクニックを厳選して紹介します。コンテスト本番はもちろん、日常的なコーディングでも役立つ内容ばかりです。ひとつずつ見ていきましょう。 %演算子を使わずに奇数・偶数を判定する 数値が奇数か偶数かを判定する最もシンプルな方法が、ビット演算AND（&）を使う方法です。数値と1とのANDを取った結果が0でなければ奇数、0なら偶数と判断できます。仕組みは単純で、すべての奇数は最下位ビット（LSb）が1になっています。1とのAND演算によりLSb以外

C++には「未定義動作（Undefined Behavior：UB）」と呼ばれる特殊な挙動が存在します。これは、ある操作を実行した際に、言語仕様上その結果が一切保証されない状態を指します。コンパイル時にはエラーとして検出されないため見落としがちですが、実行時に予期せぬクラッシュや誤動作を引き起こす重大なバグの温床となります。C++をさまざまな用途で活用したいプログラマーなら、誰もがこれらの未定義動作を把握しておくべきです。この記事では、典型的な未定義動作を含むC++コードをいくつか取り上げ、実際にどのような結果になるのかを確認していきます。多くの場合、これらのコードは実行時エラー（ランタイムエ

C++には、あるオブジェクトが特定のクラス型のインスタンスであるかどうかを直接判定する組み込みの仕組みがありません。Javaであればinstanceof演算子を使うだけで簡単に確認できますが、C++では別のアプローチが必要です。C++11にはstd::is_base_of<Base, T>という型トレイトが用意されています。これは指定したクラスが別のクラスの基底クラスであるかどうかをコンパイル時にチェックするものです。しかし、これはあくまで型同士の継承関係を調べるだけで、実行時に渡されたオブジェクトの実際の型までは検証できません。dynamic_castを使ったinstanceof

この記事では、C++において浮動小数点数をあらかじめ指定した小数点以下の桁数まで出力する方法を解説します。C++では、coutと組み合わせてsetprecisionを使用することで、出力する桁数を自由に制御できます。setprecisionは、iomanipヘッダーファイルに定義されているマニピュレータです。なお、デフォルト設定ではsetprecision(n)は「有効数字n桁」を意味します。小数点以下ちょうどn桁に固定して表示したい場合は、後述のようにfixedを併用すると便利です。サンプルコード#include <iostream> #include <iomanip&g

C++では、関数に対してinlineキーワードを使用できます。そしてC++17からは、この概念が変数にも拡張され、「インライン変数（inline variable）」という新しい機能が導入されました。インライン変数の基本的な仕組みインライン変数は、複数の翻訳単位（translation unit）で定義することが許されている点が大きな特徴です。「1つの変数を複数回定義するとODR（One Definition Rule：一意定義ルール）に違反するのでは？」と思われるかもしれませんが、心配は不要です。インライン変数もODRに従っており、同じ変数が複数の翻訳単位で定義された場合でも、コンパイラとリ

C++には、コードをより短く、高速に書くための便利な機能やテクニックが数多く隠されています。特に競技プログラミングに参加する方にとっては、これらのテクニックを覚えておくことで実装時間を大幅に短縮できます。本記事では、実践で役立つC++のトリックを一つずつわかりやすく解説していきます。 %演算子を使わずに奇数・偶数を判定する 剰余演算子「%」を使わずに数値の偶奇を判定する方法です。考え方はシンプルで、数値と1のビットごとのAND（論理積）を取ります。結果が0でなければ奇数、0なら偶数です。 この仕組みの根拠は、すべての奇数は最下位ビット（LSb）が1になっているという点にあります。1とのAND演

C++において、浮動小数点数はfloat型で4バイト、double型で8バイトというサイズを持ちます。そのため、変数に格納できる小数の桁数には限りがあります。例えば、1/3 = 0.333333… のように理論上は無限に続く数値を浮動小数点型の変数に入れると、有限の有効桁数だけが保存されます。C++の標準設定では、表示される有効数字は6桁です。つまり、何も指定しない状態では、浮動小数点数は最大6桁までしか出力されません。setprecisionで精度を変更する表示する精度を変更したい場合は、<iomanip>ヘッダーに含まれるstd::setprecisionを使用します。まずは基

共有メモリとは共有メモリとは、2つ以上のプロセス間で共有されるメモリ領域のことです。では、なぜメモリを共有したり、何らかの通信手段が必要になったりするのでしょうか。繰り返しになりますが、各プロセスはそれぞれ独立したアドレス空間を持っています。あるプロセスが、自分のアドレス空間内の情報を使って他のプロセスと通信したい場合、IPC(プロセス間通信)の技術を利用するしかありません。なお、通信は親子関係にある関連プロセス同士でも、まったく無関係なプロセス同士でも行うことができます。通常、関連するプロセス間の通信にはパイプ(Pipe)や名前付きパイプ(Named Pipe)が使われます。一方、無関係なプ

共有メモリがあるのに、なぜメッセージキューが必要なのか？共有メモリという強力なIPC手段がすでにあるのに、なぜメッセージキューが必要なのでしょうか。その理由は複数あります。理解しやすいように、いくつかのポイントに分けて整理してみましょう。メッセージキューでは、あるプロセスがメッセージを受信すると、そのメッセージは他のプロセスからは利用できなくなります。一方、共有メモリでは、複数のプロセスが同じデータに同時にアクセスできます。小さなサイズのメッセージ形式で通信したい場合に適しています。共有メモリでは、複数のプロセスが同時に通信する際、同期処理によってデータを保護する必要があります。共有メモリへの

この記事では、C++のstd::map型のオブジェクトに対して、範囲ベースforループ(range-based for loop)を使用する方法を解説します。 std::mapは、キーと値のペア(キーバリューペア)を格納できる連想コンテナです。内部ではpairオブジェクトとしてデータを保持しており、1つのキーとそれに対応する値がセットになって管理されます。キーと値の型はテンプレート引数で指定する仕組みのため、文字列や数値など、任意の型のデータを柔軟に扱えます。 範囲ベースforループを使えば、マップ内の各ペアを簡潔に反復処理することが可能です。以下のサンプルコードで、具体的な使い方を確認しまし

本記事では、C++におけるプロキシクラス（Proxy Class）について解説します。プロキシクラスとは、いわゆるプロキシデザインパターンを実現するためのクラスです。このパターンでは、あるオブジェクトが別のクラスのために「修正されたインターフェース」を提供します。具体的なコード例を見ながら、その仕組みを理解していきましょう。 課題：0と1だけを格納できる配列クラスを作りたい ここでは、「バイナリ値（0または1）しか格納できない配列クラス」を作成することを目標とします。まずは素朴な第一の試みから見てみましょう。 最初のコード例 class BinArray { int arr[10];

この記事では、C++11の機能を使ってタイマーを作成する方法を解説します。ここでは「later」というクラスを作成します。このクラスは、以下の3つの要素を受け取ります。int型：コードを実行するまでの待機時間（ミリ秒）bool型：trueの場合は即座に制御を返し、指定時間後に別スレッドでコードを実行します（非同期モード）可変引数：std::bindに渡す関数とその引数なお、chrono::millisecondsをchrono::nanosecondsやchrono::microsecondsなどに変更すれば、タイマーの精度を自由に調整できます。サンプルコード#include <func

動的初期化とは何かオブジェクトの動的初期化（Dynamic Initialization）とは、プログラムの実行時（ランタイム）にオブジェクトを初期化することを指します。つまり、オブジェクトの初期値はコンパイル時ではなく、実行時に決定・代入されます。C++では、コンストラクタに引数（パラメータ）を渡すことによって動的初期化を実現できます。この手法は、クラスのメンバ変数を実行時に初期化したい場合に特に有効です。なぜ動的初期化が必要なのかオブジェクトの動的初期化が求められる主な理由は以下の通りです。メモリを効率的に利用できる：必要なタイミングで必要な値だけを設定するため、無駄なメモリ使用を抑えられ

C言語では、freopen() 関数を使うことでリダイレクトを実現できます。この関数を利用すると、既存の FILE ポインタを別のストリームへ向けることが可能です。構文は以下のとおりです。FILE *freopen(const char* filename, const char* mode, FILE *stream)C++におけるリダイレクトの仕組みC++でも同様にリダイレクトが可能です。C++ではストリームという概念が使われており、独自のストリームを作成できるだけでなく、システム標準のストリームもリダイレクトできます。C++のストリームには主に次の3種類があります。istream: 入力

イテレータ無効化とはC++には、vector、list、set、mapなど、用途に応じたさまざまなコンテナが標準ライブラリとして用意されています。これらのコンテナを走査する際にはイテレータを使用しますが、扱い方を誤ると予期しない動作を引き起こすことがあります。特に注意が必要なのが「イテレータの無効化（invalidation）」です。コンテナを反復処理している最中に要素の追加や削除などでコンテナの構造やサイズが変化すると、イテレータが無効化され、最悪の場合は未定義動作につながります。以下のサンプルコードで、無効化が引き起こす問題を確認してみましょう。問題を引き起こすサンプルコード#includ

コンポジットパターン（Composite Pattern）は、複数のオブジェクトからなるグループを、あたかも単一のオブジェクトであるかのように扱いたい場面で活用されるデザインパターンです。 このパターンでは、オブジェクトを木構造（ツリー構造）として組み立てることで、「部分」と「全体」の両方の階層を一貫した形で表現できます。オブジェクト群のツリー構造を生成するパターンであるため、GoFデザインパターンの分類では「構造に関するパターン（Structural Patterns）」に属します。 コンポジットパターンの基本概念 コンポジットパターンでは、自分自身と同じ型のオブジェクト群を内部に保持するク

本記事では、C++における出力イテレータ（Output Iterator）について詳しく解説します。出力イテレータにはいくつかの重要な特性があり、それらは以下のようにまとめられます。コンテナ内の値を変更（書き込み）するために使用される。この種のイテレータでは、コンテナからデータを読み取ることはできない。一方向・書き込み専用のイテレータである。インクリメント（前進）は可能だが、デクリメント（後退）はできない。出力イテレータには2つの種類がある。挿入イテレータ（Insert Iterator）とostreamイテレータである。挿入イテレータ（Insert Iterator）とは挿入イテレータは、コ

この記事では、C++における双方向イテレータ（Bidirectional Iterator）の概念について詳しく解説します。双方向イテレータの主な特徴双方向イテレータは、前方イテレータ（Forward Iterator）のすべての機能に加えて、前置および後置のデクリメント演算子（--）をサポートしています。この種類のイテレータは、コンテナの末尾方向にも先頭方向にも、両方向から要素へアクセスできます。ランダムアクセスイテレータも、双方向イテレータの一種です。双方向イテレータは前方イテレータとほぼ同じ機能を持ちますが、最大の違いは逆方向（減少方向）への移動が可能であるという点です。双方向イテレータ

この記事では、有向非巡回グラフ（DAG: Directed Acyclic Graph）のランダム線形拡張（Random Linear Extension）を作成する方法を解説します。線形拡張とは、DAGの位相ソート（トポロジカルソート）に相当するものです。以下のようなグラフを例に考えてみましょう。トポロジカルソートとは有向非巡回グラフにおけるトポロジカルソートとは、頂点を線形に並べた順序のことです。有向グラフのすべての辺 u-v に対して、並び順の中で頂点 u が必ず頂点 v よりも先に現れるような順序を指します。始点の頂点は必ず終点の頂点よりも先に配置される必要があるため、処理済みの頂点を

本記事では、グラフ上の頂点間の最短経路を求めるジョンソンのアルゴリズムについて解説します。紹介するC++プログラムでは、頂点の数・辺の数・各辺のコストを入力として受け取り、すべての頂点のペア間の最短距離を距離行列として出力します。 まず、次のようなグラフを例に考えてみましょう。 このグラフにおいて、各頂点間の最短経路は以下のようになります。プログラムは頂点数・辺数、そして各辺とそのコストを入力として受け取ります。 入力 − 頂点数：3 辺数：5 辺とコスト − 1 2 8 2 1 12 1 3 22 3 1 6 2 3 4 出力 − グラフの距離行列。 081210046140 アルゴリ