C++

C++ STLにおけるスタック（stack）は、LIFO（Last In First Out：後入れ先出し）構造として実装されるコンテナです。LIFOとは「最後に入れたものが最初に取り出される」という意味で、本を一冊ずつ積み上げた山をイメージすると理解しやすいでしょう。一番上に置いた本（＝最後に挿入された要素）が最初に取り出されることから、この構造はLIFOと呼ばれています。 スタックで使える主な操作 1. top() – 最上位要素の取得 スタックの最上位（先頭）にある要素への参照を返します。要素自体は削除されません。 構文：name_of_stack.top() 引数：なし 戻り値：ス

C++のlist（リスト）とはlistは、データを順次格納するコンテナの一種で、要素に対して連続しない（非連続）メモリ領域を割り当てる点が大きな特徴です。C++におけるlistは双方向リンクリスト（doubly linked list）として実装されており、先頭と末尾の両端から要素の挿入・削除が可能です。そのため、リストを前後どちらの方向からでも走査できます。なお、単方向リンクリストを使用したい場合は、C++ STLで提供されている forward_list を利用します。listをvectorの代わりに使うメリットイテレータが正しい位置に差し掛かっていれば、listコンテナへの要素の挿入・削

三角形が与えられ、その頂点から底辺までの最小パス和を求める問題を考えてみましょう。ただし、各ステップでは、1つ下の行にある隣接する数字のいずれかにのみ移動できるという制約があります。 問題の例 例えば、次のような三角形があるとします。 [ [2], [3,4], [6,5,7], [4,1,8,3] ] この場合、頂点から底辺への最小パス和は 11 になります（2 + 3 + 5 + 1 = 11）。上から順に、各行で隣接する小さい方の数字を選んで移動していくイメージです。 アルゴリズム（動的計画法） この問題は動的計画法（DP）を使うことで効率的に解けます。ポイン

連結リスト（リンクリスト）が与えられたとき、そのリストに対して挿入ソートを行うことを考えます。例えば、リストが [9, 45, 23, 71, 80, 55] の場合、ソート後のリストは [9, 23, 45, 55, 71, 80] となります。 アルゴリズムの手順 この問題は、次の手順に従って解くことができます。 任意の値を持つダミーノード（dummy）を新しく作成します node を与えられたリストの先頭として設定します node が NULL でない間、以下を繰り返します newNode = node の次のノード、dummyHead = dummy の次のノード、prevDumm

問題概要完全二分木を考えます。各ノードは (data, left, right, next) という4つのフィールドを持っており、left は左部分木を、right は右部分木を指します。next ポインタは、同じレベル(階層)における「次のノード」を指すためのもので、右隣にノードが存在しない場合は null となります。初期状態ではすべての next ポインタが null に設定されているため、これらのリンクを適切に張り直すことが本記事の目的です。例えば、以下のような木がある場合、これを次のように変換します。解法のアプローチこの問題は、レベルごとにノードをたどりながら next ポインタを順

問題概要 次のような二分木を考えてみましょう。各ノードは (data, left, right, next) というフィールドを持っており、left は左部分木を、right は右部分木を指します。そして next ポインタは、同じ階層における一つ右隣のノードを指すものです。右隣にノードが存在しない場合は null になります。初期状態ではすべての next ポインタが null に設定されているため、これらのリンクを適切に張る必要があります。 例えば、下図のような木が与えられた場合、次のように変換されます。 解法のアプローチ この問題は、next ポインタそのものを利用して各レベルを

問題概要2つのソート済み配列 A1 と A2、および整数 k が与えられているとします。ここでペア (u, v) は「A1 から1つの要素」と「A2 から1つの要素」を組み合わせたものとして定義します。このとき、要素の合計が小さい順に k 個のペア [(u₁, v₁), (u₂, v₂), …, (uₖ, vₖ)] を求めるのが目的です。たとえば、A1 = [1, 7, 11]、A2 = [2, 4, 6]、k = 3 が入力された場合、出力は [(1, 2), (1, 4), (1, 6)] となります。解法のアプローチこの問題は優先度付きキュー（ヒープ）を活用することで効率的に解けます。ポ

問題概要 数当てゲーム（Guess Game）を考えてみましょう。ゲームのルールは次の通りです。 プレイヤー1が1からnまでの整数の中から1つの数字を選びます。プレイヤー2は、その数字を当てる役割です。 プレイヤー2の予想が外れるたびに、プレイヤー1は「選んだ数字はもっと大きい」か「もっと小さい」かを教えてくれます。 ただし、プレイヤー2がある数字xを予想して外れた場合には、xドルを支払わなければなりません。プレイヤー2が正解した時点でゲームは終了です。 この問題の目的は、相手がどの数字を選んでいても必ず当てられるようにするための最小の支払額を求めることです。 具体例 n = 10、プレ

文字列 S が与えられたとき、その文字を並べ替えることで、隣り合う2文字が同じにならないようにできるかどうかを判定します。並べ替えが可能であれば、そのような結果の中から任意の1つを出力し、不可能な場合は空文字列を返します。例えば、入力が「AAB」であれば、出力は「ABA」となります。解法のアプローチこの問題は、優先度付きキュー(ヒープ)を使った貪欲法で効率的に解くことができます。ポイントは、残りの出現回数が多い文字から順番に交互に配置していくことです。手順は以下の通りです。(整数・文字)のペアを保持する優先度付きキュー pq を作成し、マップ m を定義しますn := 文字列の長さ各文字の出現

文字列 S と単語のリスト words が与えられたとき、S の部分列（サブシーケンス）となっている words[i] の個数を求める問題です。たとえば、入力が S = "abcde"、辞書が ["a", "bb", "acd", "ace"] の場合、出力は 3 になります。これは、辞書の中に「a」「acd」「ace」の3つの単語が S の部分列として含まれているためです（"bb" は b が連続して2つ必要ですが、S 内に b は1つしかないため一致しません）。 解法のア

問題の概要difficulty[i] は i 番目の仕事の難易度、profit[i] は i 番目の仕事を完了させたときに得られる利益を表します。さらに、worker[i] は i 番目の労働者の能力を表し、この労働者は難易度が worker[i] 以下の仕事しか担当できません。各労働者が担当できる仕事は最大で 1 つですが、同じ仕事を複数人の労働者が担当することは可能です。この条件のもとで、得られる利益の合計の最大値を求めます。具体例入力が difficulty = [2,4,6,8,10]、profit = [10,20,30,40,50]、worker = [4,5,6,7] の場合、出

ある銘柄の毎日の株価を記録し、その日の「スパン」を返すAPIを考えてみましょう。ここでいう今日の株価のスパンとは、次のように定義されます。今日から過去にさかのぼって、株価が今日の価格以下であった日が連続して何日続いたかという最大の日数。例えば、7日間の株価データが [100, 80, 60, 70, 60, 75, 85] だった場合、それぞれの日のスパンは [1, 1, 1, 2, 1, 4, 6] となります。この記事では、このAPIの本体となるモジュールをC++で実装する方法を解説します。単調スタックを使ったアプローチこの問題は単調スタック（Monotonic Stack）を使うことで効

一列に並んだ木があり、i 番目の木には tree[i] という種類の果実が実っているとします。私たちは好きな木からスタートし、以下の手順を繰り返し実行します。今いる木から果実を 1 つバスケットに加えます。果実を追加できない場合は終了します。現在の木の一つ右隣の木へ移動します。右側に木が存在しない場合は終了します。バスケットは 2 つあり、それぞれどれだけの量でも運ぶことができますが、1 つのバスケットに入れられる果実は 1 種類だけという制約があります。この手順で収集できる果実の合計数を求めましょう。例えば、木が [0, 1, 2, 2] のように並んでいる場合、答えは 3 になります。2

整数の正方配列 A が与えられたとき、A を通る「落下パス（Falling Path）」の合計の最小値を求めることを考えます。落下パスとは、最初の行の任意の要素からスタートし、それ以降は各行から1つずつ要素を選んで進む経路のことです。ただし重要な制約として、次の行で選べる要素は、直前の行で選んだ列から最大でも1列しかずれていない場所（同じ列・左隣・右隣）に限定されます。 例えば、次のような行列が与えられたとしましょう。 123456789 この場合の出力は 12 になります。条件を満たす落下パスは複数存在し、[1,4,7]、[1,4,8]、[1,5,7]、[1,5,8]、[1,5,9]、[2,

整数型の配列 A が与えられたとき、要素の合計が K で割り切れる「空でない連続する部分配列」の個数を求めます。例えば、A = [4,5,0,-2,-3,1]、k = 5 の場合、出力は 7 になります。該当する7つの部分配列は [[4,5,0,-2,-3,1], [5], [5,0], [5,0,-2,-3], [0], [0,-2,-3], [-2,-3]] です。解法のアプローチこの問題は「累積和」と「剰余」を組み合わせたハッシュマップを使うことで、O(n) の計算量で効率的に解くことができます。考え方の基本は次の通りです。2つの累積和が K で割った余りを等しく持つならば、その間に対応

0と1のみから構成される配列Aが与えられ、そのうち最大K個の値を0から1へ更新できるものとします。このとき、1のみを含む最も長い（連続した）部分配列の長さを求めるのがこの問題です。 例として、A = [1,1,1,0,0,0,1,1,1,1,0]、k = 2 の場合を考えてみましょう。2つの0を1に反転すると、配列は [1,1,1,0,0,1,1,1,1,1,1] のようになり、連続する1の最長列の長さは 6 になります。 解き方：スライディングウィンドウ法 この問題はスライディングウィンドウ（2ポインタ）を使うことで、線形時間 O(n) で効率的に解けます。ウィンドウ内に含まれる0の個数

問題の概要 少なくとも3つの要素から構成され、隣り合う任意の2要素間の差がすべて等しい数列を等差数列と呼びます。例えば、次のような数列は等差数列です。 [1, 3, 5, 7, 9]（公差 2） [7, 7, 7, 7]（公差 0） [3, -1, -5, -9]（公差 -4） 一方、[1, 1, 2, 5, 7] は隣接要素間の差が一定ではないため、等差数列ではありません。 ここで、N 個の整数からなる 0 インデックスの配列 A が与えられます。この配列のスライスとは、0 ≤ P < Q < N を満たす整数のペア (P, Q) のことです。スライス (P, Q) が算術ス

ストーンゲームIIの問題概要 2人のプレイヤー、AliceとBobが一列に並んだ石の山で対戦します。各山には正の整数の石が入っており、配列 piles[i] として表されます。ゲームの目的は、最終的に最も多くの石を獲得することです。 両者は交互に手番を進め、Aliceが先攻です。初期状態では M = 1 となっています。各プレイヤーの手番では、残っている山のうち先頭から X 個（ただし 1 ≤ X ≤ 2M）を選び、そこにある石をすべて取ることができます。手番の直後には M が max(M, X) に更新されます。石がすべてなくなった時点でゲーム終了です。 例として piles = [2,7

文字列 s と整数 k が与えられた状況を考えてみましょう。「k個の重複削除」とは、文字列の中から隣接する k 個の同一文字を選んで取り除き、削除した部分の左側と右側をつなぎ合わせる操作のことです。この操作を、それ以上文字列を変更できなくなるまで繰り返し適用し、最終的に残る文字列を求めるのが本問題の目的です。 具体例で確認しよう 入力が s = deeedbbcccbdaa、k = 3 の場合を順に追ってみます。 まず eee を削除 → ddbbcccbdaa 次に ccc を削除 → ddbbbdaa さらに bbb を削除 → dddaa 最後に ddd を削除 → aa したがって

2つの整数 low と high が与えられたとき、範囲 [low, high] に含まれるすべての「ステッピングナンバー（Stepping Number）」を昇順に並べたリストを求めます。ステッピングナンバーとは、隣り合うどの桁同士も絶対差がちょうど1になる整数のことです。たとえば 321 はステッピングナンバーですが、421 は該当しません。入力が low = 0、high = 21 の場合、出力は [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21] となります。 解き方のアプローチ この問題は、DFS（深さ優先探索）によって条件を満たす数を段階的に生