C++

幅優先探索（BFS：Breadth First Search）は、与えられたグラフ上のすべてのノードを訪問するための基本的なアルゴリズムです。まず1つのノードを選択し、そこに隣接するノードを順番に訪問していきます。すべての隣接頂点の処理が完了したら、次の頂点へ移動し、同様にその隣接頂点を確認していく、という流れで探索を進めます。 競技プログラミングでは、いかに速く問題を解けるかが重要になります。C++のSTL（標準ライブラリ）を活用すれば、BFSを効率的に実装できます。その際に必要となるのがキュー（Queue）というデータ構造です。隣接するすべての頂点をキューに追加し、それらの処理が終わっ

C++では、文字列の長さを取得するために複数の方法が用意されています。C++では従来の文字配列（C言語形式の文字列）を扱うこともできますし、標準ライブラリの std::string クラスを利用することも可能です。それぞれの場面に応じて、適切な手法を選ぶことが重要です。 文字列の長さを取得する5つの方法 std::string クラスには length() 関数と size() 関数が用意されており、どちらもstring型オブジェクトの長さを取得できます。一方、C言語形式の文字列（char配列）の長さを求める場合は、<cstring> ヘッダーファイルに定義されている strlen

カクテルソート（Cocktail Sort）は、バブルソートの変種の一つです。通常のバブルソートでは常に左から右へ走査を行い、各パスで最大の要素を配列の末尾へ移動させ、次のパスで2番目に大きい要素を後ろから2番目の位置へ配置していきます。一方、カクテルソートは両方向を交互に走査する点が特徴です。まず左から右へ走査して大きな要素を右端へ送り、次に右から左へ走査して小さな要素を左端へ送ります。この往復動作が「カクテルシェイカー」のように見えることから、この名前が付いています。双方向に走査することで、「ウサギ（端に近い小さな値）」や「カメ（末尾近くにある小さな値）」と呼ばれる要素の移動が速くなり、バ

コムソートとはコムソート（Comb Sort）は、バブルソートを改良したソートアルゴリズムです。基本的な考え方はバブルソートと共通していますが、両者には重要な違いがあります。バブルソートでは常に隣接する要素同士を比較するのに対し、コムソートではあらかじめ設定された「ギャップ（間隔）」を使って、離れた位置にある要素同士を比較します。各パス（走査）が完了するたびにギャップは縮小されていきます。このとき用いられる縮小係数（シュリンクファクター）は1.3で、つまり各パスの終了後、ギャップの値を1.3で割っていくことになります。計算量（時間計算量）最良ケース：O(n log n)平均ケース：O(n²/2

この記事では、ノームソート（Gnome Sort）の動作原理について詳しく解説します。ノームソートはシンプルなソートアルゴリズムの一つで、「ノーム（庭の小人）が鉢植えの花を並べ替える様子」から名付けられたと言われています。このアルゴリズムの大きな特徴は、リストがすでにソート済みである場合に O(n) の時間で処理が完了する点です。つまり、最良ケースの計算量は O(n) となります。一方、平均ケースおよび最悪ケースの計算量は O(n²) であり、バブルソートと同程度の性能になります。ノームソートのアルゴリズムgnomeSort(arr, n)begin index := 0 wh

この記事では、「Xで割り切れる最大のK桁の整数」を求める問題をC++で解く方法を解説します。一見すると複雑そうに思えますが、実は非常にシンプルな数式だけで答えを導き出せる、アルゴリズム学習に最適な題材です。解法の基本的な考え方K桁の最大の整数は、次の公式で簡単に求められます。max = 10^k − 1例えば5桁なら「99999」、6桁なら「999999」となります。この最大値がそのままXで割り切れれば、それが答えです。もし割り切れない場合は、次の式を使うことで、Xで割り切れる最大のK桁の数を一発で計算できます。max − (max mod X)具体例：5桁かつ29の倍数となる最大の数まず、5

本記事では、配列のインデックスiからjまでの要素の合計を求める方法を解説します。これはいわゆる「範囲合計クエリ（レンジクエリ）」と呼ばれる典型的な問題です。 最も単純な方法は、インデックスiからjまでループを回して順番に合計を足していくことです。しかし、この種の範囲クエリは複数回実行されることが前提となるため、クエリごとに毎回ループで計算していると処理時間が大きくなってしまいます。 そこで有効なのが累積和を事前に計算しておく手法です。累積和を前計算しておけば、以降の範囲合計はどの範囲でも定数時間O(1)で求められます。具体的なアルゴリズムを見ていきましょう。 アルゴリズム rangeSum(

この記事では、古典的なソートアルゴリズムであるバブルソートを、再帰（リカーシブ）を用いた別のアプローチで実装する方法を解説します。一般的なバブルソートはfor文などの反復処理で記述されることが多いですが、ここでは同じ処理を再帰呼び出しで表現してみましょう。再帰バブルソートの仕組み再帰版バブルソートでは、関数を1回呼び出すたびに配列全体を走査する「1パス」が実行され、その時点での最大の要素が配列の末尾に移動します。その後、問題のサイズを1つ減らして（n-1）自分自身を再度呼び出します。そして、nが1になった時点で、それ以上ソートすべき要素が存在しないため、再帰を終了します。アルゴリズムbubbl

はじめにこの記事では、ある整数の「偶数の素因数」の合計を効率的に求める方法を解説します。例として、n = 480 という数を考えてみましょう。480 を素因数分解すると、2、2、2、2、2、3、5 となります。このうち偶数である素因数は 2 のみなので、その合計は 2+2+2+2+2 = 10 になります。一見すると、すべての因数を列挙して偶数かどうか判定する必要があるように思えますが、実はもっとシンプルな方法で解けます。解法のポイント偶数の素因数は 2 しか存在しない、という点が重要です。これを利用すると、次の手順で問題を解くことができます。数が 2 で割り切れる間、そのたびに合計に 2 を

この記事では、配列を指定した位置で分割し、分割した先頭部分を配列の末尾に移動させる方法を解説します。例として、配列の内容が {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} である場合を考えます。この配列を2つの部分に分割します。1つ目の部分はインデックス0から3まで（分割サイズ4）、2つ目の部分は残りです。先頭部分を末尾に追加すると、配列は {4, 5, 6, 7, 8, 9, 0, 1, 2, 3} のようになります。これは実質的に「左回転（left rotation）」と呼ばれる操作であり、先頭の要素を1つずつ取り出して末尾に移動する処理を、分割サイズ分だけ繰り返すことで実現

この記事では、C++のSTL（Standard Template Library）を使用して、配列のすべての逆順列を生成する方法を解説します。たとえば、(1, 2, 3) という数値列の順方向の順列と逆順列は、それぞれ以下のようになります。順方向の順列1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1逆順列3, 2, 1 3, 1, 2 2, 3, 1 2, 1, 3 1, 3, 2 1, 2, 3逆順列を求めるには、STLの prev_permutation() 関数を使用します。この関数は、現在の並びを辞書式順序で1つ前の順列に変換し、前の順列が

この記事では、C++ STLのstd::arrayコンテナに用意されているget()関数について詳しく解説します。この関数は、配列コンテナ内のi番目の要素を取得するために使用される便利な非メンバ関数です。 構文 get<i> array_name get()関数は、2つの必須パラメータを受け取ります。 1つ目はインデックスパラメータで、配列のi番目の位置を指定します。ここにはテンプレート引数として整数の定数を渡します。 2つ目は配列名（array_name）で、実際に要素を取り出す対象となる配列そのものです。 この関数は、指定されたi番目の要素への参照を返します。 なお、get()

この記事では、C++ STLのstd::arrayが提供するcrbegin()とcrend()という2つのメンバ関数について詳しく解説します。これらの関数を使うと、配列の要素を逆順に安全に走査することができます。 array::crbegin() とは array::crbegin()は、コンテナの逆順イテレータ（リバースイテレータ）を取得するための関数です。戻り値は定数（const）の逆順イテレータであり、コンテナの最後の要素を指します。 「c」が接頭辞についていることからわかるように、このイテレータは読み取り専用です。つまり、イテレータを通じて要素の値を変更しようとするとコンパイルエラーに

はじめにC++のSTL（Standard Template Library）には、固定長配列を扱うためのstd::arrayコンテナが用意されています。本記事では、そのメンバ関数であるarray::fill()とarray::swap()の役割と具体的な使い方を、サンプルコードと実行結果をもとにわかりやすく解説します。array::fill() ― 配列を指定した値で満たすarray::fill()は、配列のすべての要素を引数で指定した値で一括して上書きする関数です。配列全体を同じ値で初期化したい場合や、値をリセットしたい場合に非常に便利です。まず、配列の現在の要素を出力し、その後fill(5

双対称行列とは？本記事では、与えられた行列が「双対称行列（bisymmetric matrix）」であるかどうかを判定するC++プログラムを紹介します。双対称行列とは、正方行列において主対角線（左上から右下への対角線）と反対角線（右上から左下への対角線）の両方に対して対称な行列のことです。言い換えると、通常の対称行列（転置しても元の行列と同じ）であり、同時に中心対称な行列でもあるものを指します。以下の5×5の行列は、双対称行列の一例です。1 2 3 4 5 2 6 7 8 4 3 7 9 7 3 4 8 7 6 2 5 4 3 2 1アルゴリズムcheckBiSymmetric(mat, n)

C++では、システムの現在の日付や時刻を人間が読みやすい形式（Human Readable Form）で出力する方法が複数あります。本記事では、代表的な3つの手法をサンプルコードと実行結果とともにわかりやすく解説します。方法1：time()・localtime()・asctime() を使う最も古典的かつ広く使われているのが、<ctime>ヘッダーに含まれる標準ライブラリ関数を組み合わせる方法です。それぞれの役割は以下の通りです。time()：現在の暦時刻（カレンダー時間）を取得します。時刻は算術型（time_t型）として保持されます。localtime()：取得した時刻を、年月日

はじめに：クラスの内部構造とデフォルトコンストラクタ本記事では、C++におけるクラスの内部構造（internals）について解説します。その前提として、内部構造と密接に関わる「デフォルトコンストラクタ」の仕組みから確認していきましょう。デフォルトコンストラクタとは、引数を一切取らないコンストラクタのことです。ユーザーが定義したものも、コンパイラが自動生成したものも含まれます。では、なぜデフォルトコンストラクタが必要なのでしょうか。コンパイラがデフォルトコンストラクタを挿入するケースデフォルトコンストラクタが定義されていない場合、コンパイラは暗黙的にそれを宣言します。デフォルトコンストラクタはク

本記事では、「ボゴソート（Bogo Sort）」と呼ばれるユニークなソートアルゴリズムについて解説します。ボゴソートは「順列ソート（Permutation Sort）」「バカソート（Stupid Sort）」「スローソート（Slow Sort）」など、さまざまな名前でも知られています。ボゴソートは、実用性という点では極めて非効率なソート手法です。このアルゴリズムは「生成と検証（Generate and Test）」パラダイムに分類され、リストがソートされるまで要素の並び替え（シャッフル）を繰り返し生成し続けます。発想自体は非常にシンプルで、「リストがソート済みになるまで、ひたすら要素をシャッフ

本記事では、与えられた合計値が「互いに隣り合わないフィボナッチ数」の和として表現できるかどうかを判定し、表せる場合には実際にどの数値の組み合わせになるのかを求める方法を解説します。 例えば、合計値が10の場合、これは8と2の和として表せます。8も2もフィボナッチ数であり、しかもフィボナッチ数列の中で隣り合っていません。この性質はゼッケンドルフの定理として知られており、「任意の正の整数は、連続しないフィボナッチ数の和として必ず一意に表せる」ことを示しています。 それでは、考え方をつかむためのアルゴリズムを見ていきましょう。 アルゴリズム nonNeighbourFibo(sum) Begin

この記事では、マトリックス（2次元配列）の要素をZ字形の順序で出力する方法を解説します。Z字形の出力とは、まず1行目を左から右へ、次に右から左への対角線上の要素、最後に最終行を左から右へと出力することで、文字どおり「Z」の形に沿って要素をたどる手法です。例として、次のような4×4の行列を考えてみましょう。5 8 7 1 2 3 6 4 1 7 8 9 4 8 1 5この行列をZ字形で出力すると、結果は以下のようになります。5 8 7 1 6 7 4 8 1 5アルゴリズムの考え方処理の手順はシンプルで、次の3つのステップで構成されます。1行目のすべての要素を左から右へ出力する。対角線上の要素を