C++

はじめにこのチュートリアルでは、C++ STLのstd::listコンテナから要素を削除する方法について詳しく解説します。要素の削除には、リストの先頭の要素を取り除く pop_front() 関数と、末尾の要素を取り除く pop_back() 関数を使用します。pop_front() と pop_back() の概要pop_front()：リストの先頭にある要素を削除しますpop_back()：リストの末尾にある要素を削除しますどちらの関数も計算量は O(1) と非常に高速に動作します。ただし、戻り値は void 型であるため、削除した要素の値を直接取得することはできません。また、空のリストに

問題の概要二分木と整数 target が与えられたとき、値が target と一致するすべての葉ノードを削除することを考えます。ここで重要なのは、葉ノードを削除した結果、その親ノードが新たに葉ノードになり、かつその値が target と一致する場合には、その親ノードも同様に削除しなければならないという点です。この操作は、削除できるノードがなくなるまで繰り返し行います。例えば、下図のような二分木があり、target が 2 の場合、最終的な木は次のようになります。解法のアプローチこの問題は、再帰を用いた後順（ボトムアップ）処理によって効率的に解くことができます。具体的な手順は以下の通りです。ルー

問題概要 回文（前から読んでも後ろから読んでも同じになる文字列）が与えられます。この文字列に対して、ちょうど1文字を任意の小文字の英字に置き換え、回文ではなくなる文字列のうち辞書順最小のものを作ります。そして、その結果得られる最終的な文字列を求めてください。どうしても回文を壊せない場合は、空文字列を返します。 例えば、入力が "abccba" の場合、出力は aaccba となります。 解法のアプローチ この問題は貪欲法（グリーディ法）を使うことで効率的に解けます。辞書順最小の文字列を作るには、「可能な限り前方の文字を小さくする」という性質を利用するのがポイントです。 アル

N×M の行列が与えられたとき、左上から右下へ向かう各対角線に沿って要素を昇順に並べ替えることを考えます。例えば、次のような行列があったとしましょう。331122121112これを対角線ごとにソートすると、出力は次のようになります。111112221233解法のアプローチこの問題は「対角線上の要素を取り出してソートし、元の位置に書き戻す」というシンプルな発想で解けます。具体的には、以下の手順に従います。solve() というメソッドを定義します。引数として開始位置 si、sj と行列 mat を受け取ります。n に行数、m に列数を代入します。一時的な格納用として temp 配列を作成します。

レストランの情報が配列として与えられます。各要素 restaurants[i] は [id, 評価(レーティング), ビーガン対応, 価格, 距離] という形式を持っています。この中から、次の3つのフィルタ条件を使ってレストランを絞り込みます。ビーガン対応フィルタ:true の場合は、ビーガン対応フラグが 1 のレストランのみを対象とします。false の場合は、すべてのレストランを含めることができます。最大価格(maxPrice)フィルタ:価格がこの値以下のレストランのみを考慮します。最大距離(maxDistance)フィルタ:距離がこの値以下のレストランのみを考慮します。フィルタリング後の

問題概要0からn-1までの番号が付けられたn個の都市があるとします。配列edgesが与えられ、edges[i] = [fromi, toi, weighti] は都市fromiとtoiの間を結ぶ双方向の重み付き辺を表します。さらに、整数の距離しきい値(distance threshold)が与えられます。このとき、何らかの経路を辿って到達でき、かつその距離がしきい値以下となる都市の数が最も少ない都市を求めてください。該当する都市が複数存在する場合は、その中で最も番号の大きい都市を返します。入力例次のような入力を考えてみましょう。n = 4、距離しきい値も4であるとき、出力は3になります。その理

問題概要配列 arr が与えられているとします。私たちはいくつかの整数からなる集合を選び、その集合に含まれるすべての整数を配列から取り除くことができます。ここで求めたいのは、配列の要素の少なくとも半分が取り除かれるようにするために必要な「集合の最小サイズ」です。例として、arr = [3,3,3,3,5,5,5,2,2,7] の場合を考えてみましょう。このとき出力は 2 になります。{3,7} を選択すると、新しい配列は [5,5,5,2,2] となり、そのサイズが5（元の配列サイズ10のちょうど半分）になるためです。サイズ2の候補としては {3,5}、{3,2}、{5,2} などがあります。

整数型の配列 arr と、2つの整数 k および threshold が与えられます。このとき、サイズが k で平均が threshold 以上となる部分配列（サブアレイ）の個数を求めるのが目的です。例として、入力が [2,2,2,2,5,5,5,8]、k = 3、threshold = 4 の場合を考えてみましょう。このとき出力は 3 になります。これは、部分配列 [2,5,5]、[5,5,5]、[5,5,8] の平均がそれぞれ 4、5、6 となり、いずれも閾値 4 以上だからです。解法のアプローチ（スライディングウィンドウ）この問題は、スライディングウィンドウ（尺取り法）を使えば効率的に解

問題の概要時（hour）と分（minutes）の2つの数値が与えられます。このとき、時計の短針と長針の間にできる角度のうち、小さい方の角度（度数法）を求めます。例えば、hour = 12、min = 30 が入力された場合、答えは 165° になります。解法のアプローチこの問題を解くには、以下の手順に従います。h = 12 の場合は h := 0 とするm = 60 の場合は m := 0 とするhAngle := 0.5 × (60 × h) + m を計算する（短針の角度）mAngle := 6 × m を計算する（長針の角度）ret := |hAngle − mAngle| を求めるre

同じ長さの2つの文字列 s と t が与えられているとします。1ステップごとに、t 内の任意の1文字を選び、別の文字に置き換えることができます。このとき、t を s のアナグラムにするために必要な最小ステップ数を求めるのが課題です。注意: 文字列のアナグラムとは、同じ文字を異なる(または同じ)順序で並べ替えた文字列のことを指します。たとえば、入力が「yxy」と「xyx」の場合、出力は 1 になります。これは、わずか1文字を置き換えるだけでアナグラムにできるためです。解法のアプローチこの問題を解くために、以下の手順に従います。n := s の文字数としますマップ m を作成し、s に含まれる各文

問題概要本記事では、ProductOfNumbersというクラスを実装する方法を解説します。このクラスは、以下の2つのメソッドをサポートする必要があります。add(int num): 現在の数値リストの末尾に数値 num を追加します。getProduct(int k): 現在のリスト内の末尾 k 個の数値の積を返します。なお、getProduct が呼び出される時点で、現在のリストには必ず k 個以上の数値が存在すると仮定して構いません。動作例例えば、以下の順序でメソッドを呼び出した場合を考えてみましょう。add(3) → [3]add(0) → [3, 0]add(2) → [3, 0,

イベントの配列 events が与えられ、各要素は events[i] = [startDay_i, endDay_i] という形式で表されます。イベント i は startDay_i に始まり、endDay_i に終わります。イベント i には、startDay_i から endDay_i までの範囲(両端の日を含む)の任意の日 d に参加することができます。ただし、同じ日に参加できるイベントは1つだけという重要な制約があります。この条件のもとで、参加できるイベントの最大数を求めましょう。例えば、入力が [[1,4], [4,4], [2,2], [3,4], [1,1]] の場合、出力は

問題概要 スーパーマーケットでセールが開催されており、n人ごとに割引が適用されるというシナリオを考えてみましょう。店内には複数の商品があり、i番目の商品IDは products[i]、その商品の単価は prices[i] で表されます。 システムは来店客を順番にカウントし、n番目の客が到着したタイミングで、その客の請求額に対して割引を適用します。割引適用後はカウントがリセットされ、再び0から数え始めます。顧客はそれぞれの商品を任意の数量だけ注文します。product[i] が注文されたi番目の商品ID、amount[i] がその注文数量です。この仕組みを Cashierクラス として実装します

文字「a」「b」「c」のみから構成される文字列 s が与えられたとき、「a」「b」「c」がそれぞれ少なくとも1回出現する部分文字列の個数を返すことを考えます。 例えば、文字列が「abcabc」の場合、出力は 10 になります。条件を満たす部分文字列は「abc」「abca」「abcab」「abcabc」「bca」「bcab」「bcabc」「cab」「cabc」、そして後半部分の「abc」の合計10個です。 アプローチ：スライディングウィンドウ(尺取り法) この問題は、スライディングウィンドウと呼ばれる手法を使うことで、線形時間 O(n) で効率よく解くことができます。手順は以下のとおりです。

0からn-1までの番号が付けられたn個の二分木ノードがあるとします。ノードiは、leftChild[i]およびrightChild[i]で表される2つの子を持ちます。与えられたすべてのノードがちょうど1つの有効な二分木を構成する場合にのみ、trueを返す必要があります。ノードiに左の子が存在しない場合はleftChild[i]が-1となり、右の子がない場合も同様にrightChild[i]が-1になります。なお、この問題ではノードは値を持たず、ノード番号のみを使用することに注意してください。例えば、入力が以下のような場合を考えてみましょう。この場合、出力はtrueになります。解決のアプローチこ

問題概要整数 num が与えられたとき、積が num + 1 または num + 2 と等しくなるような2つの整数のうち、絶対差（2つの値の差の絶対値）が最小になるペアを求めます。返す順序は問われません。例えば、入力が 8 の場合を考えてみましょう。num + 1 = 9 のとき、最も近い約数のペアは [3, 3] です。num + 2 = 10 のとき、最も近い約数のペアは [2, 5] です。両者を比較すると、差がより小さいのは [3, 3] なので、これが出力となります。解法のアプローチこの問題は「約数列挙」と「差の比較」を組み合わせることで解けます。手順は以下の通りです。getDiv(

二分木のルート(root)と、先頭ノードheadを持つ連結リストが与えられたとします。連結リストのhead以降のすべての要素が、二分木内のどこかの下向きパス(downward path)に一致する場合はTrueを、一致しない場合はFalseを返す必要があります。例えば、次のような二分木があったとします。このとき、連結リストが [1, 4, 2, 6] であれば、出力は true になります。実際に、ルートの1から始まり4→2→6とたどるパスが存在するためです。解法のアプローチこの問題を解くために、再帰とメモ化(動的計画法)を組み合わせた以下の手順に従います。メモ化用のマップ dp を定義します

二分木におけるジグザグパスとは二分木のルートが与えられたとき、ジグザグパス（ZigZag Path）は以下のように定義されます。二分木内の任意のノードと、方向（右または左）を選択します。現在の方向が「右」であれば現在のノードの右の子へ移動し、「左」であれば左の子へ移動します。その後、方向を右から左へ、または左から右へ切り替えます。木の中でこれ以上移動できなくなるまで、2番目と3番目の手順を繰り返します。ここでジグザグパスの長さは「訪問したノード数 − 1」として定義されます（単一ノードの場合、長さは0です）。この記事では、与えられた二分木に含まれる最長のジグザグパスを見つける方法を解説します。

問題概要 部屋にn個の電球があり、1からnまでの番号が付けられて、左から右へ一列に並んでいます。最初はすべての電球が消えています。時刻k（kは0からn-1までの範囲）に、light[k]番目の電球を点灯させていきます。ある電球が青色に変わるのは、その電球が点灯しており、かつそれより左側にあるすべての電球も点灯している場合だけです。点灯しているすべての電球が青色になっている瞬間の数を求めるのが、この問題の目的です。 次の図のようなイメージです。 この例の出力は3となり、条件を満たすのは時刻1、2、4です。 解法のアプローチ この問題は、マップと最小ヒープ（優先度付きキュー）を組み合わせること

問題の概要ある会社にはn人の従業員が在籍しており、各従業員には0からn-1までの一意なIDが割り振られています。会社のトップ(社長)はheadIDで表されます。各従業員には必ず一人の直属の上司が存在し、それはmanager配列によって与えられます。manager[i]はi番目の従業員の直属の上司を意味し、社長の場合はmanager[headID] = -1となります。なお、組織の上下関係は木構造になっていることが保証されています。社長は緊急のニュースを全従業員に伝えたいと考えています。まず社長が直属の部下に連絡し、その部下たちがさらに自分の部下へと伝えていくことで、ニュースは組織全体へと広まっ