C++

整数のキーを持つノードで構成される二分木が与えられたとき、合計値が指定した値と一致する「ルートからリーフ（葉）までの経路」をすべて見つける問題を考えます。経路は必ず根から始まり、葉で終わる必要があります。 問題の例 たとえば、次のような二分木 [5,4,8,11,null,13,4,7,2,null,null,5,1] があり、目標の合計値が 22 だとします。 このとき、条件を満たす経路は次の 2 本です。 [[5, 4, 11, 2], [5, 8, 4, 5]] 解法のアプローチ：DFS（深さ優先探索）＋バックトラック この問題は、少し手を加えた DFS（深さ優先探索）関数で効率的に解

2つの二分木があるとします。一方の木をもう一方の木に重ねてみると、一部のノードは互いに重なり合い、残りのノードは重ならない状態になります。ここで、この2つの木を1つの新しい二分木へマージすることを考えます。マージのルールは次のとおりです。2つのノードが重なっている場合は、それらの値を合計したものをマージ後のノードの新しい値とします。どちらか一方しかノードが存在しない場合は、空でない方のノードをそのまま新しい木のノードとして使用します。たとえば、次のような2つの木が与えられたとします。このときの出力結果は以下のようになります。解法のアプローチこの問題を解くために、以下の手順に従います。メソッド名

いくつかのチップが与えられ、i番目のチップは現在、位置 chips[i] に置かれています。次の2種類の操作を、任意のチップに対して何度でも（0回でも可）実行できます。i番目のチップを左右どちらかの方向に2単位移動する（コスト0）i番目のチップを左右どちらかの方向に1単位移動する（コスト1）すべてのチップを同じ位置に集めるために必要な最小コストを求めてください。最終的な位置はどこでも構いません。例えば、チップの初期配列が [2,2,2,3,3] の場合、出力は 2 になります。4番目と5番目のチップを位置2へ移動させる際にそれぞれコスト1がかかるため、合計の最小コストは 2 となります。解法の

m × n のサイズを持つ2次元グリッドと整数 k が与えられます。ここで、グリッドに対してシフト操作を k 回実行することを考えます。シフト操作の規則は以下のとおりです。 grid[i][j] の要素は grid[i][j + 1] へ移動します 各行の末尾 grid[i][n – 1] の要素は、次の行の先頭 grid[i + 1][0] へ移動します 右下隅 grid[m – 1][n – 1] の要素は、左上隅 grid[0][0] へ移動します たとえば、次のようなグリッドがあるとします。 123456789 これを1回シフトすると、出力は次のようになります。 91234567

問題概要 片方向連結リストの先頭ノードへの参照 head が与えられるとします。連結リストの各ノードには 0 または 1 の値が格納されており、この連結リストはある数値の2進表現を保持しています。求めたいのは、連結リストが表す数値を10進数に変換した値です。 例えば、リストが [1,0,1,1,0,1] の場合、2進数「101101」は10進数では 45 に相当するため、答えは 45 となります。 解法の考え方 この問題は、以下の手順で解くことができます。 連結リストの要素を配列(ベクター)に変換する その配列を逆順に並べ替える ans = 0、temp = 1 として初期化する i を

2-3木（2-3ツリー）とは2-3木（2-3ツリー）とは、子を持つすべてのノード（内部ノード）が、「1つのデータ要素と2つの子（2ノード）」または「2つのデータ要素と3つの子（3ノード）」のいずれかを持つ木構造のデータ構造として定義されます。定義内部ノードが1つのデータ要素と2つの子を持つ場合、そのノードを「2ノード」と呼びます。内部ノードが2つのデータ要素と3つの子を持つ場合、そのノードを「3ノード」と呼びます。以下のいずれかの条件を満たすとき、かつそのときに限り、Tは2-3木であると言えます。Tが空であること。言い換えれば、Tはノードを一切含みません。Tがデータ要素aを持つ2ノードであるこ

2-SAT問題とは2-SAT（2充足可能性）問題は、各節がちょうど2つのリテラルからなる論理式に対して、すべての節を真にするような変数の割り当て（充足割り当て）が存在するかどうかを判定する問題です。対象となる論理式は次の形で表されます。f = (x1 ∨ y1) ∧ (x2 ∨ y2) ∧ … ∧ (xn ∨ yn)ここで各 xi、yi はブール変数またはその否定です。問題は「f は充足可能か？」という問いに帰着します。含意への書き換え鍵となるのは、選言（OR）を含意（→）で書き換えられるという同値関係です。次の3つの式はすべて同値です。xi ∨ yi¬xi → yi¬yi → xiそこで、各

マージソートは、配列を再帰的に2つの部分に分割し、それぞれをソートしてからマージ（併合）するアルゴリズムです。このバリエーションの一つに「3方向マージソート（3-way Merge Sort）」があり、配列を2つではなく3つの部分に分割して処理を行います。 基本概念 通常のマージソートでは、配列を半分のサイズの部分配列に再帰的に分解します。一方、3方向マージソートでは、配列を3分の1のサイズの部分配列に分解していきます。分割数が増えることで再帰の深さが浅くなる（底が3の対数になる）という特徴があります。 実行例 入力: 46, -1, -44, 79, 31, -41, 11, 20, 7

プログラミングでは、関数が返した値を検証し、その値に応じて条件分岐の処理を行いたい場面が数多くあります。従来のC++では、次のようにコードを書くのが一般的でした。// 何らかのメソッドまたは関数 return_type foo(Params); // 引数を渡して関数を呼び出し、 // 戻り値をvar1に格納する auto var1 = foo(Params); if (var1 == /* 何らかの値 */) { // 何らかの処理を行う } else { // 別の処理を行う }上記のコードは、一般的なif-elseブロックの形式に従っています。まず変数をセットアップする

このチュートリアルでは、ある数値のセットビット(1になっているビット)を、指定された範囲内で別の数値へコピーするC++プログラムについて解説します。 ここでは2つの整数 x と y が与えられます。私たちのタスクは、y の各ビットを確認し、そのビットが指定された範囲 [l, r] 内にあり、かつ1(セット状態)になっている場合に、x の対応するビットも1にセットすることです。最後に、変更後の x の値を出力します。 アルゴリズム この問題は、ビットマスクを活用することでシンプルかつ効率的に解くことができます。手順は以下の通りです。 範囲 l と r が有効な範囲(1〜32)内にあるかどうかを

本記事では、与えられた点集合から凸包（Convex Hull）を求めるプログラムについて、C++での実装を交えながら詳しく解説します。 凸包とは？ 凸包とは、与えられたすべての点を境界上または内部に含む最小の凸多角形のことです。計算幾何学における基本的な問題の一つで、画像処理や衝突判定、地理情報システムなど幅広い分野で応用されています。 グラハムスキャン（Graham Scan）の流れ グラハムスキャンは、凸包を効率的に求める代表的なアルゴリズムです。処理の大まかな流れは以下の通りです。 基準点の選択： y座標が最も小さい点（複数ある場合はx座標も小さい方）を基準点 p0 として選びます。

この記事では、C++を使って与えられた点群の凸包（Convex Hull）を求める「単調チェーンアルゴリズム（Andrews Algorithm）」について詳しく解説します。 凸包とは、与えられたすべての点を内部または境界上に含む、最小の凸多角形のことです。計算幾何学における基本問題の一つで、衝突判定、画像処理、地理情報システム（GIS）など、幅広い分野で応用されています。 単調チェーンアルゴリズムの概要 単調チェーンアルゴリズムは、次の手順で凸包を構築します。 すべての点を、x座標・同じならy座標の順で辞書式順序にソートする。 ソート済みの点を先頭から走査し、「下側の凸包」を構築する。 逆

このチュートリアルでは、与えられた点の集合に対して凸包(Convex Hull)を求めるプログラムについて解説します。凸包とは、与えられたすべての点を「境界上」または「内部」に含む最小の凸多角形のことです。計算幾何学における基本的な問題の一つで、画像処理や衝突判定、地理情報システムなど幅広い分野で応用されています。アルゴリズムの概要本プログラムでは分割統治法(Divide and Conquer)を採用しています。全体の流れは以下のとおりです。点の集合を x 座標でソートした後、左右半分に分割する各半分について再帰的に凸包を求める点数が少ない場合(5点以下)は総当たり(ブルートフォース)で直接

このチュートリアルでは、与えられた複数の座標点をすべて内部に含む長方形の座標を求めるプログラムについて解説します。 問題の概要 いくつかの座標点が与えられます。私たちのタスクは、次の条件を満たす最小の長方形を見つけることです。 すべての点が長方形の内部(または境界上)に含まれる 長方形の辺は座標軸(X軸・Y軸)に平行である このような長方形は「バウンディングボックス」とも呼ばれ、各点のX座標・Y座標の最小値と最大値から簡単に求めることができます。 解決のアプローチ 軸に平行な最小の長方形は、以下の4つの値だけで決まります。 Xmin: すべての点のX座標の最小値 Xmax: すべての点の

このチュートリアルでは、C++を使って秒数を「日・時・分・秒」の形式に変換するプログラムについて解説します。 具体的には、任意の秒数が与えられたとき、それを適切な日数、時間、分、秒へとそれぞれ変換することを目指します。 変換の考え方 時間の単位は以下のような関係になっています。 1日 = 24時間 = 86,400秒（24 × 3600） 1時間 = 3,600秒 1分 = 60秒 そこで、入力された秒数をまず 86,400 で割って「日数」を求め、その剰余に対して同様に 3,600 で割って「時間」、さらに 60 で割って「分」を算出し、最後に残った値が「秒」となります。 サンプルコ

はじめにこの記事では、ジャービスのアルゴリズム（Jarviss Algorithm、別名：ギフトラッピング法）を用いて、与えられた点集合の凸包（Convex Hull）を求めるプログラムをC++で解説します。凸包とは、与えられたすべての点を「内部」または「境界上」に含む最小の凸多角形のことです。計算幾何学における基本的な問題の一つであり、画像処理や衝突判定など幅広い分野で応用されています。ジャービスのアルゴリズムでは、まず最も左（x座標が最小）の点を選択し、そこから時計回りの方向に外周の点を順番にたどっていくことで、あたかも紙で点群を包み込むように凸包を構築します。アルゴリズムの流れx座標が最

このチュートリアルでは、1から3999までの範囲にあるローマ数字を10進数に変換するC++プログラムについて解説します。具体的には、ランダムなローマ数字が与えられたとき、それを対応する10進数（整数）に変換することを目的とします。ローマ数字の変換ルールローマ数字は以下の7つの記号で構成されています。I = 1V = 5X = 10L = 50C = 100D = 500M = 1000基本的には記号を左から右へ読みながら値を加算していきますが、小さい値が大きい値の前に置かれる場合は減算となります。例えば「IV」は5 - 1 = 4、「CM」は1000 - 100 = 900を表します。アルゴリ

このチュートリアルでは、「末尾に文字を追加する」操作と「末尾の文字を削除する」操作のみを使って、ある文字列を別の文字列に変換できるかどうかを判定するプログラムを、C++で実装する方法を解説します。 問題の概要 2つの文字列 str1 と str2、および整数 k が与えられます。求めたいのは、ちょうど k 回の追加・削除操作を組み合わせることで、str1 を str2 に変換できるかどうかです。 判定のポイント 合計長が k 未満の場合： 2つの文字列の長さの合計が k より小さければ、余った操作を「1文字削除してすぐ追加し直す」という無駄打ちで消費できるため、必ず変換可能です。 共通プレフ

問題の概要このチュートリアルでは、変更回数を最小限に抑えて、整数配列を狭義単調増加（厳密に増加する順序）の配列に変換するプログラムについて解説します。具体的には、整数配列が1つ与えられます。私たちのタスクは、要素の書き換えをできるだけ少ない回数にとどめながら、配列全体を狭義単調増加の順序にすることです。アルゴリズムの考え方この問題は、最長増加部分列（LIS: Longest Increasing Subsequence）を求める動的計画法を応用することで解けます。鍵となるのは、「変更せずにそのまま残せる要素」を見抜くための条件です。インデックス j と i（j < i）にある2つの要素を

はじめにこのチュートリアルでは、与えられた整数の各桁を「3」と「8」のみで構成されるように変換するプログラムをC++で解説します。具体的には、ある整数が与えられたとき、次のいずれかの操作を用いてすべての桁を3または8に変換することを目標とします。数値全体に1を加算または減算する特定の桁を任意の数字に直接置き換えるアルゴリズムの考え方最もシンプルで効率的なアプローチは、各桁を1つずつ確認する方法です。ある桁が「3」でも「8」でもない場合、その桁を直接「3」または「8」に書き換えればよいため、その桁につき1回の操作が必要になります。つまり、最小操作回数 = 「3」でも「8」でもない桁の個数となりま