C++

問題の概要2つの小文字のみで構成された文字列 s と t が与えられているとします。ここで、「s 内に現れる特定の文字をすべて別の文字へ置き換える」という操作を考えます。この操作は何度でも繰り返し実行できるものとし、s を t に変換できるかどうかを判定するのが目的です。例えば、入力が s = eye、t = pip の場合、出力は True となります。「e」をすべて「p」に置き換え、その後「y」を「i」に置き換えることで変換できるからです。解法のアプローチこの問題は、文字ごとの対応関係（マッピング）をハッシュマップに記録しながら文字列を走査することで解決できます。s の各文字が t のどの

この記事では、サイズNの整数型配列arr[]とQ個のクエリが与えられ、各クエリは次の2種類のいずれかであるという問題を扱います。目標は、指定インデックスの値更新と区間GCD(最大公約数)の取得を効率的に行うプログラムをC++で作成することです。 クエリの種類 タイプ1:{1, index, value} — 指定されたインデックスの要素をvalueに更新します。 タイプ2:{2, L, R} — インデックス範囲[L, R]に含まれる要素のGCDを求めて返します。 入力例 arr[] = {5, 1, 7, 3, 8}, Q = 3 Queries: {{2, 1, 4}, {1, 3,

問題概要 頂点数 N の木と、Q 個のクエリが与えられます。各クエリは 2 つの整数 i と j から構成され、木の中でノード i がノード j の祖先にあたるかどうかを判定するのが課題です。 具体例で動きを確認してみましょう。 入力 Q = 2, query[][] = {{3, 5}, {1, 6}} 出力 No Yes 解説 i = 3, j = 5 : ノード 3 はノード 5 の祖先ではない → No i = 1, j = 6 : ノード 1 はノード 6 の祖先である → Yes 解法のアプローチ 最も単純な方法は、DFS(深さ優先探索)によってノード i からすべての子孫をた

問題概要数値のリスト nums が与えられたとき、i < j < k かつ nums[i] < nums[k] < nums[j] を同時に満たすトリプレット (i, j, k) が存在するかどうかを判定します。たとえば、入力が nums = [2, 12, 1, 4, 4] の場合、出力は True になります。これは [2, 12, 4] という組み合わせが条件に一致しているためです(2 < 4 < 12)。解法のアプローチこの問題は、「接頭辞最小値(prefix minimum)配列」とスタックを組み合わせることで、O(n) の計算量で効率的に解くこと

複数のリスト（リストのリスト）が与えられたとき、それぞれのリストから1つずつ値を選び、選ばれた要素の中の最大値と最小値の差をできるだけ小さくする問題を考えます。例えば、入力が lists = [[30, 50, 90], [85], [35, 70]] の場合、90、85、70 を選ぶと 90 − 70 = 20 となるため、答えは 20 になります。この問題は、いわゆる「K個のリストをカバーする最小レンジ」問題と同様の考え方で解くことができます。各リストをソートした上で、最小ヒープ（優先度付きキュー）を使い、常に現在の最小値を追跡しながら、現在の最大値との差を順次評価していきます。アルゴリズ

問題概要 数値のリスト nums と整数 k が与えられます。このリストを k 個の空でない部分リスト（元の順序を保った連続する区間）に分割するとき、各部分リストの要素の合計のうち最も大きい値（最大合計）をできるだけ小さくしたいと考えます。求めるのは、その最大合計の最小値です。 例えば、nums = [2, 4, 3, 5, 12]、k = 2 の場合を見てみましょう。[2, 4, 3, 5] と [12] のように分割すると、合計はそれぞれ 14 と 12 になり、最大合計は 14 です。これより小さくすることはできないため、答えは 14 になります。 解法のアプローチ：二分探索 この問題

本記事では、小文字のみで構成された文字列 s を、できるだけ少ない回数で分割し、それぞれの部分文字列がすべて回文（前から読んでも後ろから読んでも同じ文字列）になるようにする問題を解説します。そして、その分割後の部分文字列の個数を求めるプログラムを C++ で実装します。 問題の概要 例えば、入力が s = levelracecar の場合を考えてみましょう。この文字列は「level」と「racecar」という2つの回文に分割できるため、出力は 2 となります。 このように、与えられた文字列全体を回文の集まりに分解するとき、必要な最小の分割数（＝部分文字列の個数）を計算するのが目的です。 解法の

問題の概要2次元行列が与えられたとき、すべての要素が同じ値を持つ最大の k × k 部分行列（正方形）を見つけ、そのサイズ k の値を求めることを考えます。例として、次の入力が与えられたとします。1183155525554555この場合、値がすべて「5」である 3 × 3 の正方形行列が存在するため、出力は 3 となります。解決アプローチ（動的計画法）この問題は、動的計画法（DP）を用いることで効率的に解くことができます。各セルについて、そこを左上の頂点とする同一値の正方形がどこまで拡張できるかを計算していきます。具体的な手順は以下の通りです。n := 行列の行数m := 行列の列数サイズ n

ソート済みで重複のない数値リストがあり、その各要素は文字列中の「ブレークポイント（区切り位置）」を表していると仮定します。このブレークポイントをもとに、次のルールに従う木を構築することを考えます。 ノードの値：各ノードは (a, b) という値を持ちます。a と b はいずれもブレークポイントであり、そのノードが文字列のインデックス区間 [a, b] を担当することを意味します。 ルートノード：根はすべてのブレークポイントを含む、すなわち文字列全体を範囲とします。 子ノードの範囲：左の子と右の子の範囲は順序が保たれ、互いに隣接（連続）し、かつ親ノードの範囲をちょうど覆うように分割されます。

2次元行列があり、各要素は地形の高さを表しているものとします。ここで雨が降り、谷間のくぼみがすべて水で満たされる状況を想像してみてください。 私たちの課題は、谷間に溜まる雨水の総量を求めることです。 たとえば、入力が次のような場合を考えてみましょう。 666864586666 この場合の出力は 3 になります。中央の高さ4のマスには2単位、その隣の高さ5のマスには1単位の水が溜まり、合計3単位となるためです。 アルゴリズムのアプローチ この問題は「外周から内側へ」処理を進めることで効率的に解けます。水は必ず外側へあふれるため、外周を起点に水位(せきの高さ)を追高さ)を追跡しながら内部へ進んで

問題の概要文字列 s と整数 k が与えられます。s の部分列(サブシーケンス)をいくつか選び、合計で k 個の一意な(重複しない)部分列を集めることを考えます。ここで、ある部分列を選択するコストは次のように定義されます。コスト = s の長さ − 選択した部分列の長さ目的は、k 個の一意な部分列を選んだときの合計コストの最小値を求めることです。k 個集めることが不可能な場合は -1 を返します。なお、空文字列も有効な部分列として扱います。たとえば、入力が s = pqrs、k = 4 の場合、出力は 3 になります。解き方の考え方コストの定義から、できるだけ長い部分列から優先的に選ぶほど合計

問題の概要 [x, y] 形式のユークリッド座標を要素とするリストが与えられます。この中から任意の2点を選んだときの2乗距離 (x1 - x2)2 + (y1 - y2)2 の最小値を求めるのが本記事の目的です。 例として、入力が coordinates = {{1, 2}, {1, 4}, {3, 5}} の場合を考えてみましょう。各ペアの2乗距離は次のようになります。 (1, 2) と (1, 4)：(1−1)2 + (2−4)2 = 4 (1, 2) と (3, 5)：(1−3)2 + (2−5)2 = 13 (1, 4) と (3, 5)：(1−3)2 + (4−5)2 = 5 し

問題の概要数値のリスト nums が与えられたとき、そのリストから作れる「奇数の長さの部分リスト（サブリスト）」すべてを対象に、それぞれの中央値を求めて合計した値を計算するプログラムを考えてみましょう。例えば、nums = [2, 4, 6, 3] が入力である場合を見てみます。奇数長の部分リストは [2]、[4]、[6]、[3]、[2, 4, 6]、[4, 6, 3] の6つです。それぞれの中央値は 2、4、6、3、4、4 となるため、合計は 2 + 4 + 6 + 3 + 4 + 4 = 23 になります。解法の考え方：2つのヒープで中央値を管理この問題を効率的に解くには、優先度付きキュー

問題概要 一列に並んだ靴下を表す数値のリスト row が与えられます。靴下には 0 から順に番号が振られており、(0, 1)、(2, 3)、(4, 5) のように「偶数番号とその次の番号」が同じペアになっています。現状では靴下はバラバラに置かれているため、各ペアが必ず隣り合うように並べ替えたいと考えます。このとき必要となるスワップ（要素の入れ替え）の最小回数を求めるのがこの問題の目的です。 入力例と並べ替えの流れ たとえば、入力が row = [0, 5, 6, 2, 1, 3, 7, 4] の場合、並べ替えの過程は次のようになります。 [0, 5, 6, 2, 1, 3, 7, 4]（初

問題の概要 木構造の辺のリストが [u, v] の形式で与えられるとします。これは頂点 u と頂点 v の間に無向辺が存在することを表しています。さらに、2つの整数 x と y も与えられます。自分は頂点 x におり、対戦相手は頂点 y に位置しています。ゲームは第1ラウンドに自分が移動し、次のラウンドで対戦相手が移動するという形で交互に進行します。対戦相手は、自分の番に移動せずその場にとどまることも選択できます。このとき、対戦相手を捕まえるために必要な最小ラウンド数を求めるのが課題です。 たとえば、入力が edges = [[0, 1], [0, 2], [1, 3], [1, 4]]、x

問題の概要 2次元グリッド(マトリックス)が与えられ、各セルには次のいずれかの値が格納されています。0は空きセル、1は壁、2は人を表します。人は上下左右の4方向へ移動するか、その場にとどまるかを選択でき、いずれも1時間単位を消費します。ここで、全員が集まるまでにかかる時間を最小化できる「移動可能なセル」を見つけ、その時間(必要な最小ステップ数)を返すことが目的です。 なお、複数の人が同じ空きセルを通過することは許され、任意の2人の間には必ず何らかの経路が存在すると仮定して構いません。 入力例 201010022020 この場合の出力は 2 となります。すべての人が matrix[1, 1]

二分木の上面図とは二分木が与えられたとき、その木を真上から見たときに見えるノードの値を「上面図（トップビュー）」と呼びます。結果は必ず左から右の順に並べて出力します。例えば、次のような入力があった場合、出力は [3, 5, 8, 6, 9] となります。これは、ノード3がノード2の真上に、ノード5がノード7の真上に位置しているため、2と7は上から見ると隠れてしまい、見えないからです。アルゴリズムの考え方この問題は、幅優先探索（BFS）と各ノードの「水平座標」を使うことで効率的に解くことができます。ルートの座標を0とし、左の子へ移動するたびに座標を-1、右の子へ移動するたびに座標を+1として管理

ここでは、ドミノ(2×1の長方形)とトロミノ(L字型)という2種類のピースを扱います。どちらのピースも、下図のように回転させて使用することができます。整数 n が与えられたとき、これらのピースを組み合わせて 2×n のボードを余りなく完全に埋める配置が何通りあるかを求めます。タイル張りのルールでは、すべてのマスが必ずいずれかのピースで覆われている必要があります。例えば入力が 3 の場合、出力は 5 になります。実際の配置例は以下の通りです(異なる文字は異なるピースを表しています)。[XYZ XXZ XYY XXY XYY][XYZ YYZ XZZ XYY XXY]解法のアプローチ:動的計画法こ

2つの小文字のみで構成された文字列 s と t が与えられたとします。このとき、s の部分列（サブシーケンス）のうち、t と完全に一致するものが何通りあるかを求めます。答えが非常に大きくなる可能性があるため、結果は 10^9 + 7 で割った余りとして返します。問題例入力が s = abbd、t = bd の場合、出力は 2 になります。「bd」という部分列は次の2通りの組み合わせで作れるからです。s[1] と s[3] を連結するs[2] と s[3] を連結する解法のアルゴリズムこの問題は動的計画法（DP）を使うことで効率的に解けます。手順は以下の通りです。剰余計算用の定数 m := 10

文字列 s が与えられたとき、s の空でない一意な部分列(サブシーケンス)の個数を求めることを考えます。答えが非常に大きくなる可能性があるため、結果は 109 + 7 で割った余りを返します。例えば、入力が s = xxy の場合、出力は 5 になります。「x」「xx」「xy」「y」「xxy」の5つの異なる部分列が存在するためです。解法のアプローチこの問題は、各文字について「その文字で終わる新しい部分列の数」を逐次計算していくことで解けます。手順は以下の通りです。m := 109 + 7(剰余を取るための定数)n := 文字列 s の長さサイズ26の配列 table を定義(各アルファベットご