C++

問題概要無限に広がるチェス盤を考えます。座標は -∞ ～ +∞ の範囲に及び、ナイトは初期状態でマス [0, 0] に配置されています。ナイトの移動は下図のように8通りあり、それぞれ「縦または横の方向に2マス、その後それと直交する方向に1マス」という動きになります。この問題では、ナイトを目標のマス [x, y] まで移動させるのに必要な最小手数を求めます。なお、必ず目的地に到達できる（解が存在する）ことが保証されています。具体例たとえば入力が x = 5、y = 5 の場合、出力は 4 になります。これは次のような経路で到達できるためです。[0,0] → [2,1] → [4,2] → [3,

問題概要 各行が非降順(昇順)にソートされた行列 mat が与えられます。このとき、すべての行に共通して現れる最小の要素を求めてください。共通する要素が存在しない場合は -1 を返します。 例として、次のような行列を考えてみましょう。 1234524581035791113579 この行列の場合、出力は 5 になります。すべての行に共通して登場する要素は 5 のみだからです。 解法のアプローチ この問題は連想配列(std::map やハッシュマップ)を使うことで効率的に解けます。基本的な考え方は、「各行を順番に走査しながら、最初の行から現在の行まで連続して出現している要素だけをカウントアップす

n番目の「醜い数（Ugly Number）」を求めるプログラムを書くことを考えます。醜い数とは、与えられた整数 a、b、c のいずれかで割り切れる正の整数のことです。 例として、n = 3、a = 2、b = 3、c = 5 の場合を見てみましょう。このとき醜い数は小さい順に [2, 3, 4, 5, 6, 8, 9, 10, …] と並び、3番目の値は 4 となるため、出力は 4 になります。 解法のポイント：二分探索と包除原理 醜い数を順番に生成していくのは非効率です。そこで「ある値 x 以下に醜い数がいくつあるか」を高速に数える手法を使います。 x 以下の醜い数の個数は、次の包除原理によ

文字列 s と、文字列中のインデックスのペアを格納した配列 pairs が与えられるとします。pairs[i] = [a, b] は、文字列における2つのインデックス（0始まり）を表します。これらのペアに含まれるインデックス同士の文字は、何回でも自由に入れ替えることができます。このとき、スワップを繰り返すことで得られる文字列のうち、辞書順で最小のものを求めてください。 たとえば、入力が s = dcab、pairs = [[0,3], [1,2]] の場合、出力は bacd になります。まず s[0] と s[3] を入れ替えると s = bcad となり、続けて s[1] と s[2] を

問題の概要同じ長さを持つ2つの文字列 s と t が与えられます。私たちの目標は、s を t に変更することです。s の i 番目の文字を t の i 番目の文字に変更する際のコストは、|s[i] - t[i]|、つまり2つの文字のASCIIコード値の差の絶対値として定義されます。さらに整数 maxCost が与えられているので、合計コストが maxCost 以下という条件を満たしながら、s の部分文字列を t の対応する部分文字列と同一に変換するとき、その最大の長さを求めなければなりません。例えば、入力が s = abcd、t = bcdf、maxCost = 3 の場合を考えてみましょう。

問題概要 n人の乗客が、座席がちょうどnつ用意された飛行機に搭乗する場面を考えます。最初の乗客はチケットを紛失してしまったため、座席をランダムに選びます。それ以降の乗客は、以下のルールに従って行動します。 チケットに記載された自分の座席が空いていれば、その座席に着席する 自分の座席がすでに埋まっている場合は、残りの空席からランダムに選ぶ このとき、n番目の乗客が自分の座席に着席できる確率を求めるのが課題です。例えば入力が2の場合、出力は0.5となります。つまり、2番目の乗客が2番目の座席を確保できる確率は0.5です(1番目の乗客が1番目の座席に座った場合に限られます)。 解き方 この問題

問題の概要不変（イミュータブル）なリンクリストが与えられたとき、各ノードの値を逆順にすべて出力することを考えます。この問題を解くためには、以下のインターフェースを使用します。ImmutableListNode ― 不変リンクリストのインターフェースであり、リストの先頭ノード（head）が与えられます。リンクリストへアクセスするために、次の2つの関数が利用できます。ImmutableListNode.printValue() ― 現在のノードの値を出力します。ImmutableListNode.getNext() ― 次のノードを返します。たとえば、リストが [0, -4, -1, 3, -5]

本記事では、C++における入力イテレータ（Input Iterator）について、その特徴と基本的な使い方をサンプルコード付きで解説します。 入力イテレータとは 入力イテレータは、STL（Standard Template Library）に存在する5種類のイテレータの中で、最も弱く、最もシンプルなカテゴリに分類されるイテレータです。 主に逐次入力操作に使用され、コンテナ内の値を1つずつ読み取りながら、読み取るたびにイテレータを次の要素へ進めていくという動作を行います。ストリームからのデータ読み込みなど、前方へ一方向に進みながら値を取得する場面で活躍します。 サンプルコード 以下は、vecto

はじめにこの記事では、C++のSTL(標準テンプレートライブラリ)における「set」コンテナへの要素の挿入と削除の方法を、サンプルコードと実行結果とともに解説します。setは連想コンテナの一種で、最大の特徴は「重複する要素を格納できない」ことと「要素が常にソートされた順序で保持される」ことです。この性質により、重複排除や整列済みデータの管理を簡単かつ効率的に行うことができます。setコンテナの主な特徴重複不可： 同じ値の要素は1つしか保持されません。自動ソート： 要素を挿入すると、常に昇順に並び替えられます。高速な操作： 内部は平衡二分探索木(赤黒木)で実装されており、挿入・削除・検索はいずれ

この記事では、C++のSTL（標準テンプレートライブラリ）を活用して挿入ソートを実装する方法を解説します。従来の挿入ソートでは、未ソート部分の要素を一つずつ比較しながら適切な位置へ移動させますが、STLを利用することでこの処理をより簡潔に記述できます。具体的には、std::upper_boundで正しい挿入位置を特定し、std::rotateで配列の未ソート部分を回転させて整列させます。挿入ソートの仕組み挿入ソートは、配列を「ソート済み部分」と「未ソート部分」に分けて考えるアルゴリズムです。未ソート部分から先頭の要素を取り出し、ソート済み部分の中で正しい位置に挿入する操作を繰り返します。std

本記事では、C++における std::sort() 関数の内部動作について詳しく解説します。std::sort() は、要素同士を比較しながら配列やコンテナを昇順にソートするための標準ライブラリ関数です。一見シンプルな関数に見えますが、その内部では「イントロソート（IntroSort）」と呼ばれる高度なアルゴリズムが採用されています。イントロソート（IntroSort）とはイントロソートは、クイックソート、ヒープソート、挿入ソートの3つのアルゴリズムを組み合わせたハイブリッド型のソート手法です。以下のような仕組みで動作します。まずクイックソートでソートを開始し、高速な平均性能を活かします。再帰

本記事では、C++プログラミングにおいて重要な概念である「イテレータの無効化(iterator invalidation)」について詳しく解説します。 コンテナオブジェクトの要素をイテレータで走査している最中に、適切な境界チェックを行わないと、イテレータが無効化されてしまうことがあります。この現象は主に、コンテナオブジェクトの形状やサイズが変化することによって発生します。 たとえば vector に push_back() で要素を追加するとき、現在の容量(capacity)を超えると、vector全体が新しいメモリ領域へコピー(再配置)されます。このとき、既存のイテレータは古いメモリ位置

はじめにこのチュートリアルでは、C++における lower_bound() 関数について詳しく解説します。lower_bound() は、C++の標準ライブラリ（<algorithm> ヘッダー）に含まれる関数の一つで、ソート済みコンテナの中から「指定した値以上となる最初の要素」へのイテレータを返します。二分探索を用いて実装されているため、要素数が多い場合でも高速に動作するのが特徴です。lower_bound() の基本仕様検索対象の範囲は事前にソートされている必要があります指定した値以上の要素が見つかった場合、その位置へのイテレータを返しますすべての要素が指定値より小さい場合は、

本記事では、C++のSTL（標準テンプレートライブラリ）を活用して、クラスカル法（Kruskals Algorithm）により最小全域木（MST: Minimum Spanning Tree）を求めるプログラムについて詳しく解説します。 クラスカル法では、連結された無向の重み付きグラフが入力として与えられ、そのグラフから最小全域木を計算することを目的とします。 クラスカル法とは クラスカル法は貪欲法（グリーディ法）に基づく代表的な最小全域木アルゴリズムです。以下の手順で動作します。 グラフのすべての辺を重みの昇順にソートします。 重みの小さい辺から順に取り出し、その辺を採用してもサイクル

はじめに この記事では、C++におけるMakefileの基本とその活用方法について解説します。 規模の大きなプログラムを1つのファイルにすべて記述するのは非効率的です。そこで一般的に行われるのが、プログラム全体を複数の.cppファイルと.h（ヘッダー）ファイルに分割し、クラスや機能ごとに整理したうえで、Makefileを使ってこれらをコンパイル・リンクして1つの実行ファイルにまとめるという手法です。 今回作成するファイル構成 main.cpp … プログラムのエントリーポイント（main関数） print.cpp … 文字列を出力するprint()関数 factorial.cpp … 階乗

C++のorder_of_key()関数とは 本記事では、C++におけるorder_of_key()関数の使い方と動作原理について詳しく解説します。 order_of_key()は、GCC拡張ライブラリ「GNU PBDS(Policy-Based Data Structures)」が提供する順序付きセット(ordered_set)のメソッドです。引数としてキーを1つ受け取り、そのセット内に存在する「指定したキーより小さい要素」の個数を返します。 内部的には赤黒木(平衡二分探索木)が使用されており、大量のデータがあってもO(log n)の計算量で高速に処理できる点が大きな特徴です。競技プログラミ

このチュートリアルでは、C++ STLにおける multiset の size() 関数について、具体的なプログラム例を交えながら詳しく解説します。size() 関数は、指定されたコンテナ（ここでは multiset）に現在格納されている要素の総数を返すメンバ関数です。multiset は重複した値を許容する連想コンテナであるため、同じ値が複数回挿入された場合も、それぞれが個別の要素としてカウントされる点に注意してください。サンプルコード#include <bits/stdc++.h> using namespace std; int main(){ multiset<

このチュートリアルでは、C++ STLにおけるmultisetのmax_size()関数について、実際のサンプルプログラムを通じてわかりやすく解説します。 max_size()関数とは max_size()は、指定したコンテナが理論上保持できる要素数の最大値を返すメンバ関数です。この値はシステムのメモリ制限やライブラリの実装に依存するため、環境によって結果が異なる場合があります。 なお、max_size()が返すのはあくまで理論上の上限値であり、実際にそのサイズまで要素を格納できる保証はありません。使用可能な物理メモリ量によって、それより少ない時点で例外が発生する可能性があります。 サンプルコ

C++におけるnegative_binomial_distributionとはこの記事では、C++の標準ライブラリに含まれる negative_binomial_distribution（負の二項分布）について、実際のコード例を交えながら解説します。negative_binomial_distribution は、<random> ヘッダーで定義されている乱数分布クラスの一つです。このクラスは、負の二項分布と呼ばれる離散確率分布に従う整数値を生成します。負の二項分布とは、「成功確率 p のベルヌーイ試行を繰り返したときに、k 回目の成功が起こるまでに発生した失敗回数」を表す確率分布

本記事では、C++ STLにおけるmultisetコンテナのupper_bound()関数について、具体的なコード例と実行結果をもとに分かりやすく解説します。 upper_bound()関数とは multisetのupper_bound()は、引数として渡した値より大きい要素のうち、最初に現れるものを指すイテレータを返すメンバ関数です。もしコンテナ内にそのような要素が存在しない場合は、コンテナの末尾（end()）を指すイテレータを返します。 multisetは重複した値を許容する連想コンテナであり、内部では常に要素がソートされた状態で保持されます。そのため、upper_bound()による検索