C++

概要 与えられた配列には重複のない整数が格納されており、各要素は 1 以上 N 以下の範囲に収まっています。配列のサイズは N−4 であるため、1 から N までの数値のうちちょうど 4 つが欠落していることになります。本記事では、その欠落している 4 つの数値を昇順で求めるアルゴリズムを解説します。 入力例と出力例 例 1 arr[] = {3, 6, 7, 4, 10} 出力: 1 2 5 8 9 例 2 arr[] = { 2, 8, 4, 13, 6, 11, 9, 5, 10 } 出力: 1 3 7 12 解法の考え方 基本のアプローチ：O(N) の補助配列を使う方法 最もシン

与えられた n 組の点の中から、辺が x 軸と y 軸に平行な正方形を構成する4点を見つけ出すのが本稿のテーマです。条件を満たす正方形が存在しない場合は「No such square」と表示します。また、候補となる正方形が複数存在する場合は面積が最大のものを選択しなければならない点に注意してください。 入力例 n = 6, points = (2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2) 出力例 Side of the square is: 3, points of the square are 2, 2 5, 2 2, 5 5, 5 解説

概念与えられた無向グラフに対して、サイズ l の独立集合（Independent Set）が含まれているかどうかを判定します。独立集合が存在する場合は「Yes」を、存在しない場合は「No」を出力します。ここで、グラフにおける独立集合とは、「互いに直接辺で結ばれていない頂点の集合」のことです。つまり、集合内のどの2つの頂点を選んでも、それらの間にエッジ（辺）が存在しない必要があります。入力例 1L = 4, graph = [[1, 0, 1, 0, 0], [0, 1, 1, 0, 0], [1, 1, 1, 1, 1], [0, 0, 1, 1, 0], [0, 0, 1, 0, 1]];出

概要二分木が与えられたとき、その二分木の指定された垂直レベル(vertical level)がソートされているかどうかを判定するのが本記事の目的です。なお、複数のノードが同じ位置で重なっている場合は、それらのノードが属するレベル内でソート済みの列を形成しているかどうかを確認します。入力例2 / \ 3 6 / \ 8 5   / 7 Level l = -1出力例Yesレベル -1 に属するノードは 3 → 7 の順に並んでおり、これはソート済みの列となっています。入力例(ノードの重なりがある場合)2 / \ 3 7 \ / 4 5 Level l = 0出力例Yesこの例では、値

概要コストの範囲(lowCost 以上 upCost 以下)と数量の範囲(lowQuant 以上 upQuant 以下)が与えられたとき、r = cost ÷ quantity を満たす指定された比率 r を実現できるかどうかを判定するのが本記事のテーマです。入出力例例1lowCost = 2, upCost = 10 lowQuant = 3, upQuant = 9 r = 3出力:Yes解説: cost = r × quantity = 3 × 3 = 9 となり、cost は [2, 10]、quantity は [3, 9] のいずれの範囲内にも収まるため、「Yes」が返ります。例2

問題の概要3種類ずつのカップ(p[])とソーサー(q[])、および棚の数mが与えられたとき、それらを「きれいに」棚へ配置できるかどうかを判定します。配置がきれいであるとみなされるためには、次の3つのルールをすべて満たす必要があります。ルール1:同じ棚にカップとソーサーを混在させてはいけません。ルール2:1つの棚に置けるカップは最大5個までです。ルール3:1つの棚に置けるソーサーは最大10枚までです。入出力例例1Input:p[] = {4, 3, 7}q[] = {5, 9, 10}m = 11Output:Yes解説:カップの総数は14個です。1つの棚に5個までしか置けないため、必要な棚数は

概念 重み付きグラフ、グラフ内の始点となる頂点、そして数値k(kは始点から終点までのパスの長さを表します)が与えられたとき、与えられた始点から始まり、任意の他の頂点(終点)で終わる単純パス(閉路を含まないパス)が存在するかどうかを判定することが課題です。以下のグラフを使って説明します。 入力例1 始点 s = 0, k = 64 出力 True この場合、0 -> 7 -> 1 -> 2 -> 8 -> 6 -> 5 -> 3 -> 4 という合計距離68の単純パスが存在し、64を超えているためtrueとなります。 入力例2 始点 s = 0

平衡二分探索木（BST）が与えられたとき、その木の中に合計が0になる3つのノード（トリプレット）が存在すれば true を返し、存在しなければ false を返す関数 is_valid_triplet() を作成することを考えます。この問題は、以下の制約のもとで設計する必要があります。 期待される時間計算量は O(n²) 追加で使用できる空間計算量は O(log n) 例えば、次のようなBSTが入力として与えられたとします。 この場合、出力は True になります。なぜなら、[-15, 7, 8] というトリプレットの合計が 0 になるからです。 解法のアプローチ この問題を効率的に解く

概要同じ長さの2つの文字列 S1 と S2 が与えられたとき、S1[0…i] と S2[i+1…n-1] をこの順で連結した結果が回文になるようなインデックス i を求めるのが本記事の課題です。条件を満たすインデックスが存在しない場合は -1 を出力します。入力例1S1 = pqrsu, S2 = wxyqp出力例11このとき S1[0..1] = pq、S2[2..n-1] = ypq となります。両者を連結した pqyqp は前後対称な文字列、つまり回文になっています。入力例2S1 = pqrst, S2 = qprqz出力例2-1どのようなインデックスで分割しても回文が成立しないため、-

概要0と1から構成される配列が与えられたとき、その中の「0」を1つだけ「1」に置き換えることで、最も長い連続した1の並び（シーケンス）を実現できる置換位置を求める問題です。このアルゴリズムでは、時間計算量O(n)、補助空間O(1)という効率的な実装が求められます。入力例と出力例まず、具体的な例を見てみましょう。入力：arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1}出力：Index 10配列のインデックスは0から始まるとし、インデックス10にある0を1に置き換えると、最も長い連続する1の並びが得られます。もう一つの例です。入力：arr[] = {1,

問題の概要 出発空港と到着空港のペア [from, to] で表される航空券のリストが与えられたとします。このとき、すべての航空券を一度ずつ使用して移動する完全な旅程を順番通りに求める必要があります。すべての航空券は、チェンナイから旅を始める一人の旅行者のものであるため、旅程は必ず「Chennai」から始まります。 たとえば、入力が [["Mumbai", "Kolkata"], ["Chennai", "Mumbai"], ["Delhi", "Bangalore"],

加重ジョブスケジューリング問題とはN個のジョブのリストがあり、各ジョブには次の3つのパラメータが与えられています。開始時刻(Start Time)終了時刻(Finish Time)利益(Profit)求めるのは、選択したジョブ同士が時間的に重ならないという条件のもとで、合計利益が最大になるジョブの部分集合です。たとえば、N = 4、J = {{2, 3, 55},{4, 6, 25},{7, 20, 150},{3, 150, 250}} という入力が与えられた場合、出力は [(2, 3, 55),(3, 150, 250)] となり、最適な利益は 305 になります。解法のアルゴリズムこの問

概念エンコードされた文字列では、部分文字列の繰り返しが「部分文字列＋繰り返し回数」の形式で表されます。例えば、暗号化された文字列が「pq2rs2」で k=5 の場合、復号化された文字列は「pqpqrsrs」となり、5番目の文字は「r」であるため、出力は「r」になります。なお、暗号化された部分文字列の繰り返し回数は2桁以上になることもあります。例えば「pq12r3」では、「pq」が12回繰り返されます。このとき、繰り返し回数の先頭に0が付くことはありません。入力例"p2q2r3", k = 6出力r復号化された文字列は「ppqqrrr」です。入力例"pq4r2ts3

問題概要二分探索木（BST）と整数 k が入力として与えられたとき、木の中で k番目に小さい要素 を見つける問題を解説します。例えば、以下のようなBSTを考えてみましょう。この木に対して k = 3 を指定した場合、出力は 15 になります。木の要素を昇順に並べると「9, 13, 15, 17, 19, 25, 27」となり、3番目の値が15であるためです。アルゴリズムの考え方二分探索木には、「中順走査（in-order traversal）」を行うと要素が昇順に訪問されるという重要な性質があります。この性質を利用し、走査中に訪問したノード数をカウントしていき、k番目に到達した時点でそのノード

ビットニック列とはビットニック列(バイトニック列)とは、最初に単調に増加し、その後に単調に減少する数列のことです。本記事では、2つの配列が与えられたときに、以下の条件を満たす最長のビットニック列をC++で求める方法を解説します。増加部分は1つ目の配列から取られ、その配列の部分列であること減少部分は2つ目の配列から取られ、その配列の部分列であること入力例と出力例例1arr1[] = {2, 6, 3, 5, 4, 6},arr2[] = {9, 7, 5, 8, 4, 3}出力:2, 3, 4, 6, 9, 7, 5, 4, 3この例では、増加部分「2, 3, 4, 6」がarr1の部分列となり

概要与えられた文字列をもとに、文字を削除または並べ替え(シャッフル)することで形成できる最長の回文を求める問題です。最長の長さを持つ回文が複数存在する場合は、そのうちのどれか1つを返せばよいこととします。入出力例例1入力: pqr出力: p または q または r例2入力: ppqqrr出力: pqrrqp または qprrpq または rqppqr など、長さ6の回文文字列例3入力: pqp出力: pqp解法のアプローチ回文文字列は、次の3つの部分に分解して考えることができます。beg(前半): 文字列の先頭側の部分mid(中央): 中央の1文字(偶数長の場合は空)end(後半): 文字列の

概要互いにほぼ同じ内容を持つ2つの配列が与えられたとします。ただし、一方の配列にはもう一方に存在しない要素が1つだけ欠落しています。この記事では、その欠落している要素を特定するアルゴリズムをC++で解説します。入力例1arr1[] = {2, 5, 6, 8, 10} arr2[] = {5, 6, 8, 10}出力例12この場合、2番目の配列から「2」が欠落しています。入力例2arr1[] = {3, 4, 5, 6} arr2[] = {3, 4, 5, 6, 7}出力例27今度は、最初の配列から「7」が欠落しています。アプローチ1：線形探索（シンプルな方法）最も単純な解法は、両方の配列を

概要整数の配列が与えられたとき、配列内の各要素について「左側で最も近い小さい要素」と「右側で最も近い小さい要素」を求め、その絶対差の最大値を計算するのが本記事の目的です。ここで重要なルールとして、ある要素の左側または右側にそれより小さい要素が存在しない場合は、0 をその要素とみなします。例えば、配列の先頭（最も左）の要素には左側に要素が存在しないため、左側の小さい要素は 0 となります。同様に、配列の末尾（最も右）の要素については、右側の小さい要素が 0 として扱われます。入力例1arr[] = {3, 2, 9}出力例12この場合、各要素ごとの結果は以下のようになります。左側の小さい要素 L

概要 0からN-1までの番号が付けられたN個の都市と、駅が設置されている都市のリストが与えられたとき、「任意の都市からその最寄り駅までの距離」の最大値を求めるのが本課題です。なお、駅のある都市は任意の順序で与えられる点に注意してください。 入力例 numOfCities = 6, stations = [2, 4] 出力 2 入力例 numOfCities = 6, stations = [4] 出力 4 1つ目の例では、6つの都市が存在し、駅がある都市が緑色で強調表示されています。この場合、最寄り駅から最も遠いのは都市0で、その距離は2です。したがって、最大距離は2となります。

概念数値のグリッドが与えられたとき、その中から最大長のスネークシーケンス(Snake Sequence)を求め、表示する問題について解説します。最大長を持つスネークシーケンスが複数存在する場合は、そのうちのどれか1つを出力すれば構いません。ここでいうスネークシーケンスとは、グリッド内の隣接する数値をつなげた列のことです。各数値に対して、その右側または下側にある数値が「+1」か「-1」の関係になっている必要があります。例えば、現在グリッド上の位置 (a, b) にいる場合、右隣の (a, b+1) の数値が ±1 であれば右へ移動でき、下の (a+1, b) の数値が ±1 であれば下へ移動でき