C++

二分探索（バイナリサーチ）とは二分探索は「半区間探索」「対数探索」「バイナリチョップ」とも呼ばれる検索アルゴリズムで、ソート済みの配列の中から目的の値が存在する位置を効率的に見つけ出します。基本的な仕組みは非常にシンプルです。まず、探したい値（ターゲット値）を配列の中央の要素と比較します。一致しなかった場合は、ターゲット値が存在し得ない半分を丸ごと排除し、残りの半分に対して同様の比較を繰り返します。この「中央との比較」と「範囲の絞り込み」を続け、ターゲット値が見つかるか、検索範囲が空になる（＝配列にその値が存在しない）かのどちらかで処理が終了します。アイデア自体は簡単ですが、正しく実装するには

BST（Binary Search Tree：二分探索木）とは、二分木の一種であり、根（ルート）の値より小さい値を持つノードがすべて左側に、大きい値を持つノードがすべて右側に配置されるデータ構造です。本記事で扱う問題「BSTの各ノードに、より大きい値をすべて加算する」は、次のように要約できます。与えられたBSTに対して、現在のノードの値よりも大きいすべてのノードの値を合計し、その合計を該当ノードに加算するというものです。問題の定義二分探索木（BST）が与えられたとき、各ノードに対して、そのノードより大きい値を持つすべてのノードの値の総和を加算する必要があります。例えば、次のようなBSTを考えま

問題の概要本記事では、「最初のn個の自然数の総和の合計」を求める問題を扱います。具体的には、1からnまでの各自然数kについて「1からkまでの合計」を計算し、それらをすべて足し合わせた最終的な値を求めます。まず、具体例を見ながら概念を理解しましょう。入力 : 4 出力 : 20 説明 : 最初の1個の自然数の合計 = 1 最初の2個の自然数の合計 = 1 + 2 = 3 最初の3個の自然数の合計 = 1 + 2 + 3 = 6 最初の4個の自然数の合計 = 1 + 2 + 3 + 4 = 10 したがって、総和の合計 = 1 + 3 + 6 + 10 = 20このように、各段階の部分和(1, 3

魔方陣の対角要素を埋める問題とは3×3の行列を考えます。この行列の対角要素（左上・中央・右下の要素）は、初期状態では空（0）になっています。行の合計、列の合計、対角線の合計がすべて等しくなるように、空いている対角要素を埋めるのがこの問題の目的です。例として、次のような行列を考えてみましょう。036505470対角要素を適切な値で埋めると、行列は次のようになります。636555474この結果、すべての行・列・対角線の合計が15で一致しており、正しく魔方陣が完成していることが確認できます。対角要素を求める計算式対角要素を x（左上）、y（中央）、z（右下）とすると、それぞれ次の式で求められます。な

文字列として一連のコマンドが与えられているとします。この文字列には、4つの方向を表す4種類の文字が含まれています。Uは上、Dは下、Lは左、Rは右を意味します。さらに、オブジェクトの初期セル位置 (x, y) も与えられます。与えられたコマンド列に従った後の、マトリックス内におけるオブジェクトの最終的なセル位置を求めるのが目的です。なお、最終的なセル位置は必ずマトリックス内に存在するものと仮定します。例として、コマンド文字列が「DDLRULL」、初期位置が (3, 4) である場合を考えてみましょう。このとき、最終位置は (1, 5) となります。アルゴリズムの考え方アプローチは非常にシンプルで

今回は興味深いアルゴリズムの問題を取り上げます。範囲 l ≤ x, y ≤ r を満たすペア（x, y）を見つけるというもので、このペアには「x が y を割り切る」という性質が必要です。条件を満たすペアが複数存在する場合は、そのうちの 1 つを出力すればよいことになっています。解法のアイデアこの問題は、実は O(1) の計算量で解くことができます。鍵となるのは、下限値 l とその 2 倍の値 2l です。その理由を考えてみましょう。y/x の最小値は 2 です。もし範囲内により大きな値（y/x ≥ 3 となる組み合わせ）が存在するなら、必ず y/x = 2 となる組み合わせも同じ範囲内に存在

本記事では、ソート済みの配列から「不動点（Fixed Point）」と呼ばれる特殊な要素を検索する方法を解説します。不動点とは、要素の値がそのインデックス（添字）と一致している要素のことです。プログラムは不動点が存在すればその値を返し、存在しない場合は -1 を返します。なお、配列には負の数が含まれることもあり、データ要素はソート済みであると仮定します。二分探索による効率的なアプローチすべての要素を順に確認する線形探索では O(n) の計算量が必要ですが、配列がソート済みであるという性質を利用すると、二分探索（バイナリサーチ）によって O(log n) という高速な計算量でこの問題を解くことが

本記事では、与えられた配列の中から「不動点（Fixed Point）」を見つける方法を解説します。不動点とは、配列の要素の値がそのインデックスと一致している箇所のことです。例えば、arr[2] = 2 のような場合、インデックス2が不動点となります。このプログラムは、不動点が存在すればその値を返し、存在しない場合は -1 を返します。なお、配列には負の数も含めることができ、要素は昇順にソートされているものとします。さらに、この問題では重複した要素が存在することを許容している点がポイントです。アルゴリズムの考え方：修正版二分探索この問題は、二分探索を使えば O(log n) の時間計算量で解くこ

この記事では、ある整数 n が与えられたとき、「x + x の各桁の合計 = n」という条件を満たす数 x を求める問題を解説します。例として、n = 21 の場合を考えてみましょう。このとき答えは x = 15 となります。なぜなら、15 の各桁の合計は 1 + 5 = 6 であり、15 + 6 = 21 となって、与えられた n と一致するからです。解き方のアプローチこの問題はシンプルな方法で解くことができます。1 から n まで順番に数を調べていき、それぞれの数について「その数自身 + 各桁の合計」が n と等しくなるかどうかを確認します。条件を満たす数が見つかった時点で処理を終了し、そ

要素数が異なる2つの配列があるとします。このとき、1つ目の配列に含まれる要素 x と、2つ目の配列に含まれる要素 y からなるペアを見つけます。このペアを選んで2つの配列間で要素を入れ替えた結果、両方の配列の合計が等しくなるようにするのが目的です。例として、配列 A が [4, 1, 2, 2, 1, 1]、配列 B が [3, 3, 6, 3] を持っている場合を考えてみましょう。A の合計は 11、B の合計は 15 です。ここで (1, 3) というペアを選び、これらの値を2つの配列間で入れ替えると、合計は次のようになります。A: [4, 3, 2, 2, 1, 1] → 合計 13B:

配列Aにn個の異なる要素が含まれているとします。この配列Aから、積が最大になるペア(x, y)を見つける必要があります。配列には正の要素だけでなく、負の要素も含まれている可能性がある点に注意しましょう。例えば、配列が A = [-1, -4, -3, 0, 2, -5] の場合、(-4, -5) のペアが最大の積(20)を持つため、これが答えとなります。負の数同士を掛け合わせると正の数になるため、このようなケースが生じます。解決のアプローチこの問題を解くには、配列を一度走査しながら以下の4つの値を追跡します。positive_max:正の要素の最大値positive_second_max:正の

はじめに 配列 A に n 個の異なる要素が格納されているとします。この配列から、2つの要素 x と y の差が指定された値 d と一致するようなペア (x, y) をすべて見つける必要があります。 例として、配列が A = [10, 15, 26, 30, 40, 70]、指定された差分が 30 である場合を考えます。このとき、該当するペアは (10, 40) と (40, 70) です。 解法：ツーポインタ法 この問題は、配列が昇順にソートされていることを前提とすれば、ツーポインタ（二重インデックス）法を使って効率的に解くことができます。まず、1つ目のポインタ「i」を先頭の要素に、2つ目の

K次元空間上にn個の異なる点が与えられているとします。ここで、nは(2, 105)の範囲、kは1〜5の範囲に収まるとします。このとき、与えられたn個の点それぞれへのマンハッタン距離の合計が最小となる点を求めるのが本記事の目的です。まず、2つの点P1(x1, y1)とP2(x2, y2)間のマンハッタン距離は、次のように定義されます。|x1 − x2| + |y1 − y2|例えば、次元が3で、(1, 1, 1)、(2, 2, 2)、(3, 3, 3)という3つの点が与えられた場合、答えは(2, 2, 2)となります。解法の考え方マンハッタン距離は各次元ごとに独立した絶対値の和として表せるため、

問題の概要ここでは、複数の要素を含む配列 A が与えられ、その中から幾何平均が最大となるサブセットを見つけることが課題となります。例として、A = [1, 5, 7, 2, 0] という配列を考えてみましょう。この場合、最大の幾何平均を持つサブセットは [5, 7] になります。解法のアプローチこの問題には便利な性質があります。すべての要素が正の数である場合、配列内で最も大きい2つの要素を選べば、それらの組み合わせが必ず最大の幾何平均を持つことが数学的に保証されています。これは、幾何平均は要素の積の n 乗根であり、正の数同士では要素数が増えるほど（1より大きい値のみなら別ですが）平均が引き下

はじめにここでは、N次の対称行列を生成する方法を解説します。この行列の各行には0からN-1までの整数が含まれ、主対角線上の要素は常に0になります。アルゴリズムの考え方この問題は非常にシンプルです。まずN×Nの行列を用意し、行i・列jの各要素について次のように値を決定します。i == j の場合（対角成分）: 0 を設定するそれ以外の場合: 1から始まるカウンタを1ずつ増やしながら値を格納するカウンタは行ごとに1へリセットされるため、各行には対角成分の0を除いて、1からN-1までの整数が必ず1回ずつ現れることになります。C++による実装例#include <iostream>usin

問題の概要二分木が与えられたとき、その中に重複するサブツリー（部分木）が存在するかどうかを判定する問題を考えてみましょう。例として、次のような二分木を取り上げます。この木には、サイズ2の同一のサブツリーが2つ存在します。さらに、それぞれのサブツリー内のDに注目すると、BDとBEもまた重複するサブツリーになっています。解決のアプローチ：木のシリアライズとハッシュこの問題は、木のシリアライズ（直列化）とハッシュテーブルを組み合わせることで効率的に解決できます。基本的な考え方は以下のとおりです。各サブツリーを間順走査（inorder traversal）で文字列としてシリアライズする空のノードには開

本記事では、C++を使ってn以下のすべての階乗数を出力する方法を解説します。 階乗数とは 階乗数（factorial number）とは、ある正の整数の階乗として表せる数のことです。たとえば、1! = 1、2! = 2、3! = 6、4! = 24、5! = 120 となるため、1、2、6、24、120 はいずれも階乗数に該当します。 アルゴリズムの考え方 n以下の階乗数を求める際、毎回ゼロから階乗を計算し直す必要はありません。初期値として fact = 1 を用意し、変数 i を 2 から順に増やしながら fact に i を掛けていくだけで、1!、2!、3!、… と次々に求められます。fa

問題の概要配列 A が与えられたとき、その中から a % b = k を満たすすべてのペア（a, b）を見つけることを考えます。たとえば、配列 A = [2, 3, 4, 5, 7]、k = 3 の場合、条件を満たすペアは (7, 4)、(3, 4)、(3, 5)、(3, 7) となります。ここで注意したいのは、(a, b) が順序付きペアであるという点です。つまり (3, 4) と (4, 3) は別々の候補として扱われ、それぞれ剰余演算の結果が k と一致するかどうかが個別に判定されます。解法のアプローチこの問題は、ブルートフォース（総当たり）法によって解くことができます。手順は以下のとお

配列Aが与えられたとき、その中から積が等しくなる2つのペア(a, b)と(c, d)、つまりab = cdを満たす組み合わせを見つける問題を考えます。例えば、配列A = [3, 4, 7, 1, 2, 9, 8]の場合、(4, 2)と(1, 8)というペアが条件を満たします。実際に4×2 = 8、1×8 = 8となり、積が一致していますね。この問題を効率的に解くには、ハッシュテーブル（C++ではunordered_map）を活用します。すべてのペアの積を順に計算し、同じ積がすでにハッシュテーブルに登録されているかどうかを確認することで、条件を満たすペアを検出できます。アルゴリズムの手順iを0か

問題の概要容量 X の容器に、水と別の液体が混ざった混合液が入っているとします。この混合液に含まれる水の割合は W% です。ここで、水を追加して水の割合を Y% まで引き上げたい場合、何リットルの水を加えればよいのでしょうか?例えば、X = 125、W = 20、Y = 25 という条件の場合、必要な水の量は 8.33 リットルとなります。計算式の導出元の混合液に A リットルの水を加えると、混合液の総量は X + A になります。このとき、混合液中の水の総量は次の式で表せます。(元の水の量) + A = (X の W%) + A一方、新しい混合液における水の割合は Y% なので、水の量は (