C++

単方向連結リストと整数 k が与えられたとき、リスト内の要素数を n として、n/k 番目の要素を求める関数を作成することを考えます。割り算の結果が小数になった場合は、切り上げた値を採用します。たとえば、リストが 1, 2, 3, 4, 5, 6 で k = 2 の場合を考えてみましょう。このとき n = 6 なので、6/2 = 3 番目のノード、すなわち値 3 が出力されます。アルゴリズムの考え方この問題は、2つのポインタを組み合わせたテクニックで効率的に解くことができます。手順は次の通りです。temp と fracPoint という2つのポインタを用意し、それぞれ NULL とリストの先頭

問題の概要ある年 Y が与えられたとき、Y とカレンダーが完全に一致する次の年を見つける問題を考えます。例えば、2017年のカレンダーは2023年のカレンダーと同一になっています。年 X が過去の年 Y と同一の暦年であるとみなされるためには、次の2つの条件を満たす必要があります。X が Y と同じ曜日から始まることY が閏年なら X も閏年、Y が平年なら X も平年であることアルゴリズムの考え方基本的な発想は、翌年から1年ずつ順番にチェックしていくことです。その際、開始曜日が何日分ずれたかを累積で追跡します。1年が経過するごとに、その年の日数を7で割った余りだけ曜日がずれます。具体的には、

連結リスト内の2番目に大きい要素とはこの記事では、連結リスト（リンクリスト）の中から2番目に大きい要素を効率的に求める方法を解説します。数値データを持つn個の異なるノードで構成されたリストを想定してください。例えば、リストが [12, 35, 1, 10, 34, 1] のような場合、最大値は35であり、その次に大きい値である 34 が求めるべき答えとなります。このアルゴリズムは、配列から2番目に大きい要素を探す処理と基本的な考え方は同じです。リストを先頭から末尾まで一度だけ走査し、各ノードの値を比較しながら「最大値」と「2番目に大きい値」の2つの変数を順次更新していくことで、時間計算量 O(

この記事では、リンクリストの末尾から2番目の要素を1回の走査（シングルトラバーサル）で取得する方法を解説します。例えば、リストが [10, 52, 41, 32, 69, 58, 41] という要素を持っている場合、末尾から2番目の要素は 58 となります。アルゴリズムの考え方この問題を効率的に解くには、2つのポインタを使用します。1つは現在のノードを指すポインタ（curr）、もう1つは現在位置の直前のノードを指すポインタ（prev）です。curr の next が NULL になるまで両方のポインタを同時に進めていき、ループが終了した時点で prev が指しているノードこそが、求めていた末尾

問題の概要 0から9までの値を含む数字の配列が与えられます。この問題では、配列内のすべての数字を使って2つの数値を作り、その合計が最小になるようにすることが求められます。重要な制約として、与えられた配列のすべての数字を必ず使用しなければなりません。 例 入力配列が {7, 5, 1, 3, 2, 4} の場合、最小合計は 382 となります。これは、135 と 247 という2つの数値を作成できるためです（135 + 247 = 382）。 アルゴリズムの考え方 この問題は貪欲法（グリーディ法）で解くことができます。合計を最小にするには、小さい桁の数字ほど大きな位（上位の桁）に配置するのが最

問題文各ノードが数値を持つ二分木が与えられます。この問題では、ある葉ノードから別の葉ノードまでのパスの合計として考えられる最小値を求めることがタスクです。例以下の二分木を見てみましょう。この木における最小パスの合計は -6 です。具体的には、次の経路に対応します。(-4) + 3 + 2 + (-8) + 1アルゴリズムこの問題を解くポイントは、再帰呼び出しの中で次の2つの値を管理することです。現在のノードを根とする部分木における「根から葉までの最小パス合計」葉ノード同士を結ぶ「葉間の最小パス合計」訪問した各ノードXに対して、Xの左部分木と右部分木それぞれの「根から葉までの最小合計」を求めます

問題概要 数値が三角形状に配置された構造が与えられます。頂点から最下段まで移動する際、各ステップで「下の行の隣接する数値」にのみ移動できるものとします。このとき、通過する数値の合計が最小となる経路の和を求めてください。 例 入力が以下の場合を考えます。     5   7 3  8 1 2 9 6 4 5 このとき最小の合計は 13 となり、その経路は次のとおりです。 5 + 3 + 1 + 4 アルゴリズム 動的計画法（DP）のメモ化テクニックを利用します。 メモ化用として、1次元配列 memorization を

問題の概要正の整数からなる長さ n の配列と、ある数値 k が与えられます。「k 以下の数値」をすべて配列内で隣り合うように集めるために、最低何回のスワップ(要素の入れ替え)が必要かを求めてください。入力例たとえば、入力配列が {1, 5, 4, 7, 2, 10}、k = 6 の場合を考えてみましょう。このとき必要なスワップは 1 回だけです。具体的には、7 と 2 を入れ替えることで、6 以下の要素(1, 5, 4, 2)がすべて連続して並ぶようになります。解法のアプローチこの問題は、スライディングウィンドウ(二ポインタ)のテクニックを使うことで O(n) で効率よく解くことができます。手

問題の概要 0と1のみで構成された配列が与えられます。この配列内に存在するすべての「1」を連続したブロックとしてまとめる（グループ化する）ために必要な、最小のスワップ（要素の入れ替え）回数を求めるのが課題です。 例 入力配列が {1, 0, 1, 1, 0, 1} の場合、必要なスワップ回数は 1回 です。先頭の0と末尾の1を入れ替えることで、すべての1を連続して並べることができます。 アルゴリズムの考え方 この問題は、次の手順で効率的に解くことができます。 まず、配列内の1の総数を数えます。これを x とします。 すべての1をグループ化すると、最終的に長さ x の連続した区間に1が集まる

問題概要0と1の個数が等しく、長さが偶数のバイナリ文字列が与えられます。この文字列を「交互文字列(隣り合うどの2文字も同じ文字にならない状態)」に変換するために必要な最小のスワップ回数を求めてください。例例えば、str = 11110000 の場合、必要なスワップ回数は 2回 です。2回の入れ替えで 10101010 のような交互文字列に変換できます。アルゴリズムの考え方文字列の偶数インデックス(i % 2 == 0)と奇数インデックスにそれぞれ存在する「0」の個数を数えます。それぞれ evenZeroCnt、oddZeroCnt とします。同様に、偶数インデックスと奇数インデックスに存在する

問題文 0と1のみを含むn個の整数からなる配列が与えられます。この配列を「前半がすべて0、後半がすべて1」という形に分割するために必要な最小のトグル回数（0を1に、または1を0に切り替える操作）を求めてください。 例 例えば、arr[] = {1, 0, 0, 1, 1, 1, 0} の場合、必要なトグル回数は2回です。具体的には、先頭の「1」と末尾の「0」をそれぞれ切り替えます。 アルゴリズム 問題を注意深く観察すると、インデックス0からn-1の間に必ず境界点が存在し、その点より左側にはすべての0が、右側にはすべての1が配置されるべきであることが分かります。 この規則に当てはまらない

問題の概要整数の配列が与えられたとき、その配列から取り出せるすべてのサブセット（部分集合）について要素全体のAND（ビットごとの論理積）を計算し、その中で最小となるAND値を求めて出力するのが課題です。例配列 arr[] = {1, 2, 3, 4, 5} の場合、2要素からなるサブセットのAND値は次のようになります。(1 & 2) = 0 (1 & 3) = 1 (1 & 4) = 0 (1 & 5) = 1 (2 & 3) = 2 (2 & 4) = 0 (2 & 5) = 0 (3 & 4) = 0 (3 & 5)

問題の概要n個の正の整数からなる配列が与えられたとき、サイズが2以上の部分配列の中で、「部分配列の最大値 + 最小値」の合計が最小になる値を求めるのがこの問題です。例たとえば、配列が arr[] = {10, 5, 15, 7, 2, 1, 3} の場合、「2 + 1」を加算したときの「最大値 + 最小値」の合計は 3 となり、これが求める最小値です。アルゴリズム部分配列に要素を追加しても、「最大値 + 最小値」の合計がより小さくなることはありません。配列の最大値は、要素を追加しても決して減少しません。より大きな要素を追加した場合にのみ増加します。そのため、長さ2の部分配列だけを考えるのが常に

問題文2つの整数 p と q が与えられたとき、次の2つの条件を同時に満たす最小の数 x を求めることが課題です。q % x = 0（x は q を割り切る）x % p = 0（x は p で割り切れる）もし条件を満たす数が存在しない場合は、-1 を出力します。具体例p = 3、q = 66 の場合、答えは 3 となります。 66 % 3 = 0 3 % 3 = 0アルゴリズムの考え方この問題は、数学的な性質を使うことで非常にシンプルに解くことができます。ある数 x が条件を満たすならば、x は p の倍数であり、かつ q は x の倍数です。したがって、q は必ず p で割り切れることになり

問題概要整数の配列が与えられたとき、配列内のペアの中でXOR値が最小となるペアを見つける問題です。例例えば、配列 arr[] = {10, 20, 30, 40} が与えられた場合を考えてみましょう。各ペアのXOR値を計算すると以下のようになります。(10 ^ 20) = 30(10 ^ 30) = 20(10 ^ 40) = 34(20 ^ 30) = 10(20 ^ 40) = 60(30 ^ 40) = 54この結果から、最小のXOR値は 10 であり、これはペア「20 と 30」に対応することがわかります。アルゴリズム最もシンプルなアプローチは、全探索（ブルートフォース）です。配列から

問題の概要 各ノードが可変個の子ノードを持つ木（n分木）が与えられたとき、その木をミラー（左右反転した木）に変換する方法を解説します。ミラー化とは、各ノードの子ノードの並び順を左右逆にすることを指します。 ミラー化の例 例として、次のようなn分木を考えます。 この木をミラー化すると、以下のように反転されます。 アルゴリズムの考え方 ミラー化は再帰を使うとシンプルに実装できます。手順は以下のとおりです。 手順 1. ノードがNULLの場合は何もせずに終了します。2. 子ノードが1つ以下の場合、反転しても変化がないためそのまま返します。3. 各子ノードに対して再帰的にミラー化を適用します。4

問題の概要 連続する偶数を含む整数配列 even[] と、連続する奇数を含む整数配列 odd[] が与えられます。ただし、それぞれの配列から1つずつ要素が欠落しています。この記事では、その欠落している要素を効率的に求めるアルゴリズムとC++での実装方法を解説します。 入力例 even[] = {10, 8, 6, 16, 12} odd[] = {3, 9, 13, 7, 11} この場合、 偶数配列で欠落している数は「14」 奇数配列で欠落している数は「5」 アルゴリズム この問題は、等差数列の和の公式を利用することで、配列を一度走査するだけで解くことができます。手順は以下の通りです。

問題概要 ある単語の順列(並べ替え)のうち、いくつかがリストとして与えられます。本来存在するはずの順列のうち、このリストに含まれていない「欠けている順列」をすべて見つけるのが本記事の目的です。 例 順列リスト = { ABC, ACB, BAC, BCA } の場合、 欠けている順列は { CAB, CBA } となります アルゴリズム 与えられた文字列をすべて集合(std::set)に格納する 考えられるすべての順列を生成し、もう一つの集合を作る 2つの集合の差分を計算して返す C++による実装例 #include <bits/stdc++.h> using namespa

問題文配列と2つの数値 M・K が与えられます。このとき、配列の中からサイズ K の重複しない部分配列を選び、そのうち最大 M 個の合計値を求めることが課題です(配列の要素の順序は変更されません)。ここで、K は部分配列のサイズ、M は選ぶ部分配列の個数を表します。配列のサイズは m × k より大きいものと仮定して構いません。また、配列全体のサイズが k の倍数でない場合は、末尾の部分配列を部分的に採用することも可能です。入力例たとえば、配列が {2, 10, 7, 18, 5, 33, 0}、N = 7、M = 3、K = 1 である場合を考えます。このとき選択される部分集合は次の通りです

整数 n が与えられたとき、その数に対するメビウス関数（Möbius function）の値を求めるのが本記事の目的です。 メビウス関数とは？ メビウス関数は数論における重要な関数の一つで、μ(n) として表され、次のように定義されます。 μ(n) = 0 … n が1つ以上の「繰り返し素因数」（同じ素因数を2回以上含む）を持つ場合 μ(n) = 1 … n = 1 の場合 μ(n) = (-1)^k … n が k 個の異なる素数の積で構成される場合 具体例 入力：N = 17 出力：-1 説明：素因数は 17 のみ、k = 1 (-1)^k → (-1)^1 = -1 入力：N