C++

この記事では、配列内の各要素に対して「それより大きい値のうち最も近い値」を求める方法を解説します。ある要素 x より大きな値が配列内に存在する場合、その中で最小のものが答えとなります。存在しない場合は -1 を返します。 例として、配列が [10, 5, 11, 6, 20, 12] の場合、結果は [11, 6, 12, 10, -1, 20] になります。20 より大きな値は配列内に存在しないため、-1 を出力します。 解決アプローチ この問題は、C++ STL の set を使うことで効率的に解けます。set は平衡二分探索木を基に実装されており、常に要素をソートされた状態で保持します。

このチュートリアルでは、C++を用いて深さ優先探索（DFS）のトラバーサル手順を段階的に出力するプログラムについて解説します。出力には、バックトラッキング（探索の巻き戻し）の過程も含め、DFSの実行中に発生するすべてのステップが表示されます。DFSの実行中は、各ノードを走査すると同時に、親ノードと使用したエッジ（辺）の情報を記録していきます。走査の過程で隣接ノードがすでに訪問済みである場合、そのノードへの移動も含めて、DFSの各ステップとして出力することができます。アルゴリズムの流れこのプログラムの基本的な考え方は以下の通りです。1. 各ノードの訪問状態を管理する配列を用意し、すべて「未訪問」

問題の概要ある整数が与えられたとき、その数を割り切る桁（各桁の数字）の個数を数える問題です。例として、数が 1012 の場合を考えてみましょう。この場合、答えは 3 となります。1、1、2 の3つの桁がそれぞれ 1012 を割り切れるためです。解法のアプローチこの問題を解くには、剰余演算（% 演算子）を使って数の各桁を1つずつ取り出し、元の数がその桁の値で割り切れるかどうかを判定します。割り切れる場合はカウンターを1つ増やします。なお、桁が 0 の場合は 0 で割ることができないため、その桁はスキップ（無視）します。アルゴリズムの流れ元の数のコピーを作成し、0 になるまでループを繰り返します。

はじめにこの記事では、数値の立方根（3乗根）を求める方法を解説します。例えば、27という数値の立方根は3です。ここでは、標準ライブラリの関数に頼らず、独自のロジックでこの問題を解決します。具体的には「二分探索（バイナリサーチ）」の手法を活用します。アルゴリズムの考え方まず、許容誤差（しきい値）として threshold = 0.000001 を設定します。その上で、以下の手順に従って処理を進めます。左端の値（left）を 0、右端の値（right）を対象の数値として初期化する中央値を mid = (left + right) / 2 として計算する|数値 − mid³| が threshold

このチュートリアルでは、与えられた二分木(binary tree)において、ある葉ノードから別の葉ノードまでの最長パスを出力するプログラムについて解説します。 言い換えると、二分木の直径(diameter)に含まれるすべてのノードを出力することが目的です。ここでいう直径(または幅)とは、ある端のノードからもう一方の端のノードまでの最長パス上に存在するノードの数として定義されます。 解決のアプローチ この問題は、以下の手順で解くことができます。 高さ関数による直径の計算: 各ノードに対して「左部分木の高さ + 右部分木の高さ + 1」を評価し、これが現在の最大値より大きければ、そのノードを直径

0からn-1までの範囲の数値が格納されたリストがあるとします。同じ数値は何度でも繰り返し出現する可能性があります。ここで求めたいのは、追加のメモリを使用せずに、繰り返し現れる数値をすべて検出することです。 例として、リストが [5, 2, 3, 5, 1, 6, 2, 3, 4, 1] の場合を考えてみましょう。このとき答えは 5, 2, 3, 1 となります。 解法のアプローチ この問題を解くには、リスト内の各要素 e に対して、以下の手順を実行します。 sign := A[e の絶対値] を確認する sign が正の値であれば、その値を負に変更する すでに負の値であれば、その数値は重複し

このチュートリアルでは、与えられた二分木（バイナリツリー）の中から、奇数レベルに存在するノードを出力するC++プログラムについて解説します。 本プログラムでは、ルートノードのレベルを「1」と定義し、それ以降のレベルは交互にカウントしていきます。つまり、レベル1・3・5…といった奇数番目の階層に属するノードが出力の対象となります。 例として、以下のような二分木が与えられた場合を考えてみましょう。 この二分木の場合、奇数レベルに存在するノードは 1, 4, 5, 6 となります。 アルゴリズムの考え方 実装には再帰呼び出しを利用します。ルートから探索を開始し、現在のレベルが奇数かどうかをブール

問題の概要6種類の異なる数値からなるリストがあり、そのうち1つの数値だけが5回繰り返し出現しています。つまり、配列には合計10個の要素が存在することになります。この重複している数値を、たった2回の比較だけで見つけ出すのが本記事の課題です。例えば、リストが [1, 2, 3, 4, 4, 4, 4, 4, 5, 6] の場合、重複している数値は 4 なので、出力は「4」となります。アルゴリズムの考え方ここでは、配列が昇順にソートされているものとします。合計10個の要素の中に同じ数値が5個連続して並んでいる場合、そのブロックは必ずインデックス3から5の範囲のいずれかに位置します。これは、5個の連続

問題の概要 n個の要素からなる元の配列があるとします。しかし手元にあるのは、実際の配列における隣り合う2つの要素のXOR値だけです。さらに、元の配列の最初の要素は既知であるとします。 例えば、元の配列が a, b, c, d, e, f であった場合、与えられる配列は次のようになります。 a^b, b^c, c^d, d^e, e^f 解法のポイント：XORの性質 最初の要素 a が分かっていれば、残りのすべての要素を順番に求めることができます。鍵となるのはXOR演算の性質です。x = a ^ b という値が与えられたとき、同じ a ともう一度XORを取ると、 x ^ a = (a ^ b)

概要2つの配列AとBが与えられたとき、配列Aには存在するが配列Bには存在しない要素をすべて見つける方法を解説します。AとBをそれぞれ集合（セット）とみなすと、この操作は「差集合（Set Difference）」の計算に相当します。C++では、標準ライブラリの std::set_difference アルゴリズムを使うことで、この差集合を簡単かつ効率的に求めることができます。set_differenceを使う際のポイントstd::set_difference は <algorithm> ヘッダで定義されているアルゴリズムです。使用する際は、以下の点に注意しましょう。入力となる両方の範

Excelの列名はアルファベットで構成されています。Aから始まり、Zの次はAA、ABと続き、ZZの後はAAA、AABとZZZまで進み、さらにその後も続いていきます。つまり、列番号1は「A」、列番号26は「Z」、列番号27は「AA」に対応します。本記事では、列番号が与えられたときに、対応する列名（アルファベット）を求める方法を解説します。例えば、列番号が80であれば「CB」になります。 アルゴリズムの考え方 数値nが与えられた場合、まず26で割った余りを求めます。この問題は26進数への変換に似ていますが、Excelの列名には「0」に相当する文字が存在しないため、少し工夫が必要です。 余りが0の

この記事では、配列の中で最小の要素が何回出現するか（頻度）を求める方法を解説します。例として、配列の要素が [5, 3, 6, 9, 3, 7, 5, 8, 3, 12, 3, 10] である場合を考えてみましょう。この配列の最小値は 3 であり、その出現回数は 4 回です。したがって、出力は 4 となります。解決のアプローチこの問題を解く手順は非常にシンプルで、以下の2ステップで構成されます。1. まず、配列全体を走査して最小値を見つける2. 次に、その最小値と一致する要素の個数を数えるこの方法の時間計算量は O(n) であり、配列を2回走査しますが、線形時間で処理が完了するため効率的です。

問題の概要 配列 A が与えられたとき、その配列を「合計が等しい2つのサブ配列」に分割できるかどうかを判定します。例えば、要素が [6, 1, 3, 2, 5] の配列であれば、[6, 1] と [2, 5] という2つのサブ配列に分けることができ、それぞれの合計はどちらも 7 で等しくなります。 アルゴリズムの考え方 この問題は、次の手順に従うことで簡単に解くことができます。 まず、配列内の全要素の合計(total_sum)を求めます。 次に、配列を先頭から順に走査しながら、それまでに読み取った要素の累積和(so_far_sum)を更新していきます。 各位置 i において、「2 × so

数Nと整数kが与えられたとき、Nをk個の数（1より大きい数）の積として表現できるかどうかを判定する方法を解説します。例えば、N=54、k=3が与えられた場合、54 = 2 × 3 × 9 と分解できるため「2, 3, 9」のように出力します。表現できない場合は、その旨を出力します。アルゴリズムの考え方この問題を解くには、まずNのすべての素因数を求め、それらをvectorに格納します。1より大きいk個の数を得るには、vectorのサイズがk以上であるかを確認します。サイズがk未満の場合は「-1」を返して表現不可を示します。サイズがk以上であれば、最初のk-1個の因数をそのまま出力し、最後の数は残

いくつかの要素を含む配列 A があるとします。ここに、値 X と整数 k も与えられます。この課題は、配列 A の中から X に最も近い k 個の要素を見つけることです。なお、X が配列内に存在する場合は、その要素自体は出力に含めません。 例として、A = [12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56]、X = 35、k = 4 とすると、出力は「30, 39, 42, 45」になります。 解法の考え方：二分探索を活用する この問題を効率的に解くには、二分探索（バイナリサーチ）の手法を利用します。二分探索によって「クロスオーバーポイ

ソートされていない整数型の配列A、基準となる値X、そして個数kが与えられたとします。この課題の目的は、配列Aの中からXに最も近いk個の要素を見つけ出すことです。ただし、Xが配列内に存在する場合、その要素は出力から除外されます。例として、配列 A = [48, 50, 55, 30, 39, 35, 42, 45, 12, 16, 53, 22, 56]、X = 35、k = 4 が与えられた場合、出力は 30, 39, 42, 45 となります。この問題を効率的に解くには、ヒープ(優先度付きキュー)データ構造を利用します。配列全体をソートするO(n log n)のアプローチと比べ、ヒープを使え

問題の概要 いくつかの要素を含む配列 A があるとします。この配列 A の中から最大の要素を見つけたいのですが、条件演算子を一切使用してはならないという制約が課されています。例えば、A = [12, 63, 32, 24, 78, 56, 20] という配列が与えられた場合、求める最大要素は 78 です。 解決のアプローチ：ビット演算を活用する この問題を解くカギとなるのがビット単位のAND演算です。基本的な考え方は次の通りです。 まず、すべてのビットが 1 になっている特殊な値 INT_MAX を配列に 1 つ追加します。 続いて、最上位ビット（第31ビット）から最下位ビット（第0ビット）

問題の概要辞書と文字列 s が与えられたとします。このとき、文字列 s から一部の文字を削除(つまり残りの文字の順序を保ったまま)することで作成できる、辞書内の最長の単語を見つけるのが目的です。例えば、文字列 s が apbreoigroakml で、辞書が {prog, ram, program} の場合、答えは program になります。これは program の各文字が s に順番どおりに現れている(部分列となっている)ためです。解決のアプローチこの問題を解くには、次の手順で進めます。まず、辞書内のすべての単語を走査します。次に、各単語について「その単語が与えられた文字列 s の部分列

問題の概要 1からnまでの整数が格納された循環配列を考えます。最初の要素から数え始め、2つおきに要素を削除していったとき、最後に残る要素を求めるのがこの問題です。例えば、入力が5の場合、配列は [1, 2, 3, 4, 5] となります。1から開始して2つおきに削除を進めると、配列の状態は以下のように変化します。 1 0 3 4 5 1 0 3 0 5 0 0 3 0 5 0 0 3 0 0 この結果、最後まで残る要素は 3 であることがわかります。 再帰を使った解法 この問題は、再帰的な漸化式を用いることで効率的に解くことができます。 まず、nが偶数の場合を考えてみましょう。1周目で 2,

文字列 str と、検索対象となる文字 ch が与えられたとします。この課題では、文字列の中に ch が最後に出現する位置（インデックス）を見つける必要があります。例えば、文字列が「Hello」で、検索する文字が ch = l の場合、l はインデックス2と3に出現するため、最後のインデックスは 3 となります。解決のアプローチこの問題を解くには、文字列を右から左へ（末尾から先頭へ）順番に走査します。各位置の文字が l と一致しなければインデックスを1つずつ減らしていき、一致する文字が見つかった時点で処理を停止し、そのインデックスを結果として返します。もし文字列全体を走査しても一致する文字が見