C++

問題概要根がノード0であるような木構造を考えます。この木には、次の情報が与えられています。ノードの総数：nodesi番目のノードの値：value[i]i番目のノードの親：parent[i]求めたいのは、「ノードの値の合計が0になる部分木」をすべて削除した後、木に残っているノードの個数です。たとえば、下図のような木を考えてみましょう。ノードは全部で7つありますが、出力は2になります。これは、値が0であるノード3を根とする部分木と、ノード2を根とする部分木（4 + (-2) + (-1) + (-1) = 0）が削除対象となり、最終的に残るのがノード0とノード1だけだからです。解法の考え方この問題

ここでは、以下のような操作を持つイテレータクラスを設計することを考えます。ソート済みの重複のない小文字英字からなる文字列と、数値 combinationLength を引数に取るコンストラクタを定義します。辞書順において次の長さ combinationLength の組み合わせを返す next() 関数を定義します。次の組み合わせが存在する場合にのみ true を返す hasNext() 関数を定義します。使用例たとえば、次のように入力された場合を考えてみましょう。CombinationIterator iterator = new CombinationIterator(xyz, 2); i

問題の概要区間のリストが与えられ、リスト内の他の区間に包含されている（カバーされている）すべての区間を取り除いたうえで、最後に残った区間の個数を返すことを考えます。ここで、区間 [a, b) が区間 [c, d) に包含されるとは、c <= a かつ b <= d が成り立つ場合を指します。たとえば、入力が [[1,4],[3,6],[2,8]] の場合、出力は 2 になります。このとき区間 [3,6] は [2,8] に完全に含まれているため削除され、残るのは [1,4] と [2,8] の 2 つの区間です。解法のアプローチこの問題は、区間を終了時刻でソートしたうえでスタックを

問題概要 m × n の行列 mat と整数 threshold(閾値)が与えられます。このとき、要素の合計が閾値以下となる正方形の中で最大の辺の長さを求めてください。条件を満たす正方形が存在しない場合は 0 を返します。 例えば、次のような入力が与えられたとします。 1132432 1132432 1132432 1132432 1132432 1132432 閾値が 4 の場合、出力は 2 となります。上の表の左上、および下の表の左下にある 2×2 の領域(青・緑色部分)は、合計が 1 + 1 + 1 + 1 = 4 となり閾値以下です。一方、3×3 の正方形の合計は 1

問題概要 文字列 s が与えられたとき、次の条件を満たす部分文字列の中で、出現回数が最大となるものの回数を求める問題です。 部分文字列に含まれる異なる文字の種類数が maxLetters 以下であること 部分文字列の長さが minSize 以上 maxSize 以下であること たとえば、入力が s = aababcaab、maxLetters = 2、minSize = 3、maxSize = 4 の場合、答えは 2 になります。これは、部分文字列 aab が元の文字列中に 2 回出現しており、異なる文字が 2 種類（maxLetters 以下）、長さも 3 で指定範囲内という条件を満たし

本記事では、二分木（バイナリツリー）が与えられたときに、最も深い階層にある葉ノード（子を持たないノード）の値の合計を求めるアルゴリズムを、C++のコード例とともにわかりやすく解説します。問題の概要例えば、以下のような二分木が与えられたとします。この木の場合、最も深い葉ノードは「7」と「8」であるため、求める出力は 7 + 8 = 15 となります。解法のアプローチこの問題は、DFS（深さ優先探索）による再帰的な走査と、各深度ごとの値の合計を記録するマップ（map）を組み合わせることで、シンプルかつ効率的に解くことができます。アルゴリズムの手順深さごとの合計値を格納するマップ m と、最大深度を

問題の概要2つの二分探索木（BST：Binary Search Tree）が与えられたとき、両方の木に含まれるすべての要素を昇順に並べたリストを返すことを考えます。例えば、次のような2つの二分探索木があるとします。木1：[2,1,4]木2：[1,0,3]この場合、出力は [0,1,1,2,3,4] となります。重複する値（この例では「1」）もそのまま保持される点に注意してください。解決のためのアプローチこの問題は、各BSTに対して反復的な中順走査（inorder traversal）を行い、マージソートのように2つの走査結果を統合することで効率的に解けます。手順は以下の通りです。結果を格納する

問題概要 非負整数からなる配列 arr が与えられ、最初は配列の指定された開始インデックスに位置しています。現在インデックス i にいるとき、i + arr[i] または i - arr[i] へジャンプすることができます。このとき、値が 0 であるインデックスに到達可能かどうかを判定してください。ただし、どの時点でも配列の範囲外へジャンプすることはできません。 例えば、入力が arr = [4,2,3,0,3,1,2]、開始位置が 5 の場合、出力は true になります。5 → 4 → 1 → 3 または 5 → 6 → 4 → 1 → 3 という移動経路で、値が 0 のインデックス 3

正整数からなる配列 arr と、queries[i] = [Li, Ri] の形式で与えられるクエリ配列があるとします。各クエリ i に対して、Li から Ri までの要素のXOR（arr[Li] XOR arr[Li+1] XOR ... XOR arr[Ri]）を計算し、すべての結果を格納した配列を返す必要があります。例えば、入力が [1,3,4,8]、クエリが [[0,1],[1,2],[0,3],[3,3]] の場合、出力は [2,7,14,8] となります。これは、配列内の各要素を2進数で表すと、1 = 0001、3 = 0011、4 = 0100、8 = 1000 となるためです。

問題概要m × n の行列 mat と整数 K が与えられたとき、各要素 answer[i][j] が「i − K ≤ r ≤ i + K」かつ「j − K ≤ c ≤ j + K」を満たすすべての要素 mat[r][c] の合計となるような、新しい行列 answer を求めます。ただし、(r, c) は行列内の有効な位置である必要があります。入力例たとえば、次のような 3 × 3 の行列が与えられたとします。123456789ここで k = 1 の場合、出力は次のようになります。122116274533243928例えば左上の要素 12 は、自身の値 1 と、範囲内に存在する右隣の 2・下隣

二分木が与えられたとき、「偶数値の祖父母」を持つノードの値の合計を求める問題を考えてみましょう。ここでいうノードの祖父母とは、その親の親のことを指します(存在しない場合もあります)。もし偶数値の祖父母を持つノードが一つも存在しない場合は、0 を返します。例として、次のような二分木を考えます。この場合の出力は 18 になります。図の赤いノードが「偶数値の祖父母を持つノード」であり、青いノードが「偶数値の祖父母」となるノードです。解法のアプローチこの問題を解くために、以下の手順に従います。各ノードの親を記録するためのマップ parent を定義します。ノードとその親を受け取るメソッド solve(

問題概要3つの正の整数 a、b、c が与えられたとき、a と b の一部のビットを反転して (a OR b == c) を成立させるために必要な最小の反転回数を求めます。ここでの OR は、ビット単位の論理和(ビットごとの OR 演算)を指します。「反転(フリップ)操作」とは、2進数表現において任意の1ビットを 1→0 または 0→1 に変更することです。たとえば、a = 0010、b = 0110、c = 0101 の場合、反転後は a = 0001、b = 0100 となり、a OR b = 0101 = c が成立します。解法のアプローチこの問題は、各ビット位置を独立に評価することで解け

本記事では、C++ STLに含まれる std::is_final テンプレートの仕組み、構文、具体的な使用例について詳しく解説します。 is_final は、<type_traits> ヘッダーファイルで定義されているテンプレートの一つで、C++14以降で利用できます。このテンプレートを使うと、指定した型 T が final クラス（継承できないクラス）であるかどうかをコンパイル時に判定できます。 C++におけるfinalクラスとは？ final 指定子を付けて宣言されたクラスのことを「finalクラス」と呼びます。finalクラスは、それ以上継承して新しい派生クラスを作ることがで

この記事では、C++ STLに用意されているstd::is_fundamentalテンプレートの仕組み、構文、具体的な使用例について詳しく解説します。is_fundamentalは、<type_traits>ヘッダーファイルに定義されているテンプレートの一つで、指定した型Tが「基本型（fundamental type）」であるかどうかをコンパイル時に判定するために使用されます。基本型（Fundamental Type）とは？基本型とは、コンパイラ自体にあらかじめ組み込まれている組み込み型のことです。代表的なものとして、int、float、char、doubleなどが挙げられます。こ

本記事では、C++ STLに用意されているstd::is_podテンプレートの仕組み、構文、そして具体的な使用例について詳しく解説します。 is_podは、<type_traits>ヘッダーで定義されているテンプレートです。このテンプレートを使うことで、指定した型TがPOD(Plain Old Data)型であるかどうかをコンパイル時に判定できます。 POD(Plain Old Data)とは何か？ POD(Plain Old Data)型とは、古いC言語にも存在していたような、単純で機械的なデータ表現を持つ型のことです。intやdoubleといったスカラー型も、すべてPOD型に含

本記事では、C++ STLに含まれるstd::is_pointerテンプレートの仕組み、構文、そして具体的なコード例について詳しく解説します。 is_pointerは、<type_traits>ヘッダーファイルで定義されているテンプレートの一つです。このテンプレートを使用すると、指定した型Tがポインタ型であるかどうかをコンパイル時に判定できます。C++11以降で利用可能なタイプトレイト（型特性）機能の一部であり、テンプレートメタプログラミングなどで活用されます。 ポインタとは？ ポインタとは、別の型のアドレス（メモリ上の場所）を保持する非静的型のことです。言い換えれば、メモリ空間

この記事では、C++ STLに用意されている std::is_signed テンプレートの仕組み、構文、そして具体的な使用例について詳しく解説します。 is_signed は <type_traits> ヘッダーファイルに定義されているテンプレートで、指定された型 T が「符号付き型」であるかどうかを判定するために使用します。 符号付き型とは？ 符号付き型とは、正負の符号情報を持つ基本的な算術型のことです。すべての算術データ型は、「符号付き」と「符号なし」のいずれかに分類されます。 たとえば、負の値を表現したい場合には符号付き型を使用します。 -1 は符号付き int -1.0

この記事では、C++ STLに含まれるstd::is_unsignedテンプレートの仕組み、構文、そして具体的なコード例について詳しく解説します。is_unsignedは、<type_traits>ヘッダーファイルで定義されているテンプレートの一つです。このテンプレートを使うことで、指定した型Tが「符号なし（unsigned）型」であるかどうかをコンパイル時に判定できます。C++における符号なしデータ型とは？符号なしデータ型とは、「値が負になることがない」と分かっている場合に使用する型のことです。例えば、学籍番号やID、乱数のシード値などが該当します。型を符号なしとして扱いたい場合

本記事では、C++ STLに含まれる std::is_void テンプレートの仕組み、構文、具体的な使用例について詳しく解説します。is_void は、<type_traits> ヘッダーファイルで定義されているテンプレートです。このテンプレートを使うことで、指定した型 T が void 型であるかどうかをコンパイル時に判定できます。C++におけるvoid型とは？簡単に言えば、void は「空」や「無」を意味します。関数を void 型として宣言した場合、その関数は何も値を返さないものとみなされます。また、void ポインタを宣言することも可能です。void ポインタは、指し示す先

この記事では、C++ STLにおけるisnormal()関数の動作、構文、そして具体的な使用例について詳しく解説します。isnormal()は、<cmath>ヘッダーファイルに定義されている関数で、指定した数値が「正規化数（ノーマル数）」であるかどうかを判定するために使用されます。C++11以降で利用可能であり、float・double・long doubleの各浮動小数点型に対応したオーバーロードが用意されています。正規化数（Normal Number）とは？ある実数が正規化数であるとは、その値がゼロ（0）、無限大（Infinity）、非数（NaN）、あるいは非正規化数（サブノー