C++

問題の概要ある鉄道駅に到着するすべての列車の到着時刻と出発時刻が与えられたとき、どの列車も待ち時間なく停車できるようにするために必要なプラットフォーム（ホーム）の最小数を求めるのがこの問題です。入力としては、列車の到着時刻を格納した配列と、出発時刻を格納した配列の2つが与えられます。例えば以下の入力の場合、最低でも3つのプラットフォームが必要になります。列車到着時刻出発時刻列車109:0009:15列車209:3511:45列車309:4011:05列車411:0012:00列車514:3018:15列車618:0019:00アルゴリズムこの問題は、時刻を並べ替えて同時進行する列車数を数えると

問題の概要デカルト平面上に N 個の点が与えられます。いくつかの点を削除して、残ったすべての点が「任意のひとつの軸の片側」に収まるようにしたいとき、削除が必要な点の数の最小値を求めるのが本問題の目的です。たとえば、入力が {(10, 5), (-2, -5), (13, 8), (-14, 7)} だったとします。ここで (-2, -5) を削除すれば、残りの点はすべて X 軸より上側に位置することになります。したがって、この場合の答えは 1 となります。アルゴリズム考え方はとてもシンプルです。点を軸の片側に集めたいなら、「反対側にある点をすべて取り除けばよい」からです。具体的には次の手順で解

問題文正の整数 N と X が与えられます。この課題では、N を X のべき乗の和(X⁰ + X¹ + … + Xⁿ)として表現し、使用するべき乗の項数を最小にすることが求められます。和が N と等しくなるために必要な、べき乗の最小個数を出力してください。たとえば、N = 15、X = 3 の場合、「3」のべき乗を 3 つ使って次のように表せます。15 = (32 + 31 + 31)アルゴリズム以下の考え方に基づいて最終結果を計算します。1. x = 1 の場合、答えは n そのもの(n = 1 + 1 + … と n 回の加算で表現) 2. 任意の数 n は n = x * a + b(0

正の整数 n が与えられたとき、その数の合計となるすべての正の数の組み合わせを求めることを考えます。ここで必要なのは「組み合わせ」であり、「順列」ではない点に注意してください。例えば n = 4 の場合、答えは [1, 1, 1, 1]、[1, 1, 2]、[1, 3]、[2, 2]、[4] の5通りになります。アプローチ：再帰を利用した解法この問題は再帰（リカージョン）を使うことで効率的に解くことができます。組み合わせを一時的に格納するための配列を用意し、再帰呼び出しを通じてその配列を順に埋めていきます。重複する順列を避けるため、各組み合わせの要素は必ず昇順に格納されるようにします。具体的に

はじめに この記事では、二分木（バイナリツリー）において、指定された2つのレベル番号の間に存在するノードをすべて出力するC++プログラムを解説します。 具体的には、二分木と出力範囲となる下限レベル（low）・上限レベル（high）が与えられたとき、その範囲に含まれるすべてのノードの値を表示します。ここでは、ルートノードをレベル1として扱います。 アルゴリズムの考え方 この問題は、キューを用いたレベル順走査（幅優先探索：BFS）で効率よく解くことができます。ポイントは、各レベルの末尾に「マーカーノード」を配置し、レベルの境界を検知できるようにすることです。 ルートノードとマーカーノードをキュー

問題の概要整数の配列が与えられたとき、その部分集合（サブセット）から作り出せるすべての異なる合計値を求め、昇順に出力する方法を解説します。この問題は、配列の要素の合計値が比較的小さい場合に、動的計画法を使って効率的に解くことができます。例として、配列 [1, 2, 3] を考えてみましょう。考えられるすべての部分集合は {}、{1}、{2}、{3}、{1, 2}、{2, 3}、{1, 3}、{1, 2, 3} であり、それぞれの合計値は 0, 1, 2, 3, 3, 5, 4, 6 となります。重複する値を取り除くと、出力は 0, 1, 2, 3, 4, 5, 6 となります。アプローチ：動的

二分木の上面図（トップビュー）とは このチュートリアルでは、与えられた二分木の上面図に現れるすべてのノードを出力するC++プログラムについて解説します。 二分木において、あるノードが上面図に表示されるのは、そのノードが属する「水平距離」において最初に現れるノードである場合です。水平距離は次のように定義されます。 ノード x の左の子ノードの水平距離：x − 1 ノード x の右の子ノードの水平距離：x + 1 言い換えれば、木を真上から見下ろしたときに視界に入るノードだけが上面図に現れることになります。 アルゴリズムの考え方 この問題を解くには、レベル順走査（幅優先探索）を利用します。レベ

この記事では、与えられた集合のすべての部分集合を表示する方法を解説します。例えば、集合が {1, 2, 3} である場合、その部分集合は {}, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3} の8種類になります。すべての部分集合を集めた集合は「べき集合（power set）」と呼ばれ、要素数 n の集合に対してべき集合は 2n 個の要素を持ちます。 アルゴリズムの考え方：ビット演算を活用 この問題はビット演算を使うと非常にシンプルに解けます。0 から 2n - 1 までの整数をカウンターとしてループ処理し、各反復でカウンターの i 番目のビッ

はじめに このチュートリアルでは、「隣接する2つの数が互いに素ではなく、かつ連続する3つの数が互いに素となる」ような数列を出力するC++プログラムについて解説します。 問題の概要 整数Nが与えられたとき、109未満のN個の整数を出力する必要があります。出力する数列は、以下の2つの条件を満たさなければなりません。 条件1: 隣接する2つの数は互いに素でない（最大公約数が1より大きい） 条件2: 連続する3つの整数の組は互いに素である（最大公約数が1） 例えば、N=4が与えられた場合、両方の条件を満たす数列は次のようになります。 6 15 35 14 この出力を検証してみましょう。 gcd(

このチュートリアルでは、二分木（バイナリツリー）において、ルートノードから指定されたノードまでのパスを出力するプログラムについて解説します。すべてのノードが一意な値を持つ二分木が与えられた場合、ルートノードから特定のノードに到達するまでの完全なパスを出力することが求められます。解き方のアプローチこの問題は再帰を利用することで効率的に解決できます。二分木を走査しながら、目的の要素を再帰的に探索し、同時にその要素へ至る経路を記録していきます。具体的な手順は以下のとおりです。現在訪問しているノードの値を、パスを格納する配列に追加します。現在のノードの値が探索対象と一致した場合は、探索成功として tr

本記事では、与えられた3つの座標から、面積がゼロではない平行四辺形を完成させるために必要な「4点目」の座標候補をすべて求める方法を解説します。A、B、Cという3点が与えられている場合、平行四辺形の構成として考えられるのは、次の3パターンだけです。 AB と AC を辺とし、BC を対角線とするケース AB と BC を辺とし、AC を対角線とするケース BC と AC を辺とし、AB を対角線とするケース つまり、3つの座標が決まれば、平行四辺形を形成できる4点目の座標は最大でも3通りしか存在しません。平行四辺形には「向かい合う辺は平行で長さが等しい」という重要な性質があるため、AD =

はじめに本記事では、二分木のルートノードから、木に存在する他のすべてのノードへの経路を出力するC++プログラムについて詳しく解説します。問題の概要このプログラムでは、整数Nが与えられ、二分木には1からNまでの要素が含まれているものとします。ノード1が二分木のルートノードです。したがって、私たちのタスクは、ルートノードから二分木内の他の各ノードまでの、考えられるすべての経路を出力することです。解法のアプローチこの問題を解く鍵となるのは、完全二分木の性質です。ノードiに対して、その左の子ノードは「2 * i」、右の子ノードは「2 * i + 1」として計算できます。この性質を利用し、バックトラッキ

文字列のリスト（辞書）とパターン文字列が与えられ、そのパターンに一致する文字列を辞書からすべて見つける問題を考えてみましょう。例えば、辞書が [abb, xyz, aab, kmm]、パターンが stt である場合、結果は abb と kmm となります。これは、パターンが「最初に1文字、続いて同じ2文字」という構造を持っているため、同じ構造を持つ文字列だけが該当するからです。解決のアプローチこの問題を効率的に解くには、パターンをエンコードします。エンコードの際、パターンに一致する辞書内の単語は、パターンと同じハッシュ値を持つように設計します。具体的には、各文字を「出現順に0から始まる番号」に

文字列の中に「1(0+)1」という形式のパターンが含まれていると仮定します。ここで「(0+)」は、1個以上の「0」が連続して現れることを意味します。この記事では、文字列からこのパターンをすべて検出する方法を解説します。パターン同士が重なり合う場合もカウントの対象とします。なお、対象の文字列はバイナリ文字列であるとは限らず、数字と小文字の英字のみで構成された文字列を扱います。例として、文字列が「1101001」の場合を考えてみましょう。この場合、「101」と「1001」の2つのパターンが見つかります。解決のためのアプローチこの問題は、以下の手順に従って解くことができます。文字列内のすべての文字c

問題概要重複のない正の整数からなるソート済み配列が与えられます。この中から、整数の公比をもつ等比数列(幾何級数)を形成するすべてのトリプル(3つ組)を見つけましょう。たとえば、配列が [1, 2, 6, 10, 18, 54] の場合、求めるトリプルは (2, 6, 18) と (6, 18, 54) であり、どちらも公比 3 の等比数列になっています。解き方の考え方この問題は、配列の2番目の要素から順に各要素を「中央の要素」として固定し、それより左(小さい側)と右(大きい側)の要素を探索することで解けます。中央の要素 arr[j] が等比数列の真ん中になるためには、左右の要素 arr[i]、

はじめに 本記事では、C++の標準テンプレートライブラリ（STL）を活用して、指定された範囲内に存在する素数をすべて出力するプログラムを解説します。 ここでは、2つの整数 a と b が与えられたとき、その間に含まれるすべての素数を見つけて表示することを目標とします。素数の生成には、古典的かつ高速なアルゴリズムである「エラトステネスのふるい」をサブルーチンとして利用し、求めた素数は vector に格納してから一括して出力します。 アルゴリズムの流れ エラトステネスのふるいは、n 以下の素数を効率的に列挙できる手法です。2 から順に素数を確定させながら、その倍数をふるい落としていくことで、計算

この記事では、配列内の各要素に対して「最も近い大きい値」を効率的に検索する方法を解説します。ある要素 x より大きい値が配列内に存在する場合、その中で最も小さい値（次に大きい要素）をその要素の答えとし、存在しない場合は -1 を出力します。例として、配列が {10, 5, 11, 10, 20, 12} の場合、結果は {11, 10, 12, 11, -1, 20} となります。最大値の 20 より大きい要素は配列内に存在しないため、20 に対しては -1 が出力されます。解決のアプローチこの問題は C++ STL の set（セット）を使うと簡単に解決できます。set は二分探索木をベース

このチュートリアルでは、与えられた二分木において、ルートノードからすべてのリーフノード(葉ノード)への経路を出力するプログラムを、C++で再帰を使わずに実装する方法を解説します。例として、次のような二分木を考えてみましょう。この二分木には、34・55・29という3つのリーフノードが存在します。したがって、ルートノードからリーフノードへの経路は3つあることになります。アルゴリズムのアプローチこの問題は、再帰に頼らない反復的なアプローチで解くことができます。手順は以下のとおりです。スタックを用いて、二分木を前順走査(先行順走査)します。走査の過程で、各ノードの親ノードへのポインタをマップ(std:

このチュートリアルでは、C++を用いて最長共通部分文字列（Longest Common Substring）を求めて出力するプログラムについて詳しく解説します。最長共通部分文字列とは2つの文字列AとBが与えられたとき、両方の文字列に共通して現れる最も長い「連続した」文字の並び（部分文字列）を見つけ出すのがこの問題の目的です。例えば、「helloworld」と「worldbook」という2つの文字列が与えられた場合、共通する最長の部分文字列は「world」となります。アルゴリズムの考え方（動的計画法）この問題は動的計画法（DP）を使うことで効率的に解くことができます。手順は以下の通りです。2次元

このチュートリアルでは、二分木（バイナリツリー）において、根（ルート）から葉（リーフ）までの最短パスのうち最初に見つかったものを出力するC++プログラムについて解説します。 ここでは、すべてのノードが異なる値を持つ二分木が与えられ、その木の中で根ノードから葉ノードまでの最短経路を見つける必要があります。 この問題を解くには、キュー（queue）を使って二分木をレベル順走査（幅優先探索）し、最短パス上のノードを記録する方法が有効です。具体的には、最も浅いレベルにある最初の葉ノードに到達した時点で探索を終了し、記録しておいた親ノード情報をたどることで、最短パスを出力します。 アルゴリズムのポイント