C++

問題概要 この問題では、隣接リストとして表現された有向グラフが与えられます。課題は、BFS（幅優先探索）を使って、ある始点の頂点から他のすべての頂点への経路を見つけるプログラムを作成することです。 BFS（Breadth First Search：幅優先探索）とは、グラフを幅方向に広げながら頂点を巡回していくアルゴリズムです。探索が行き止まりに達したときに、次に探索を開始すべき頂点を覚えておくためにキューを使用するのが特徴です。 具体例を使って問題を確認してみましょう。 入力 − 出力 S A <= S B <= A <= S C <= S D <= C &l

この記事では、ソート済み配列 arr[] と整数値 x が与えられたときに、配列内の「フロア（floor）」を見つけるプログラムをC++で作成する方法を解説します。 フロアとは？ ソート済み配列 arr における x のフロアとは、配列 arr[] の要素の中で、x 以下である最大の要素のことです。 具体例で問題を理解しよう 入力：arr[] = {2, 5, 6, 8, 9, 12, 21, 25}, x = 10 出力：9 説明： 上記の配列において、10 以下である最大の数は 9 です。したがって答えは 9 となります。 解法1：線形探索によるシンプルなアプローチ 最も簡単な解決策は、配

この問題では、整数要素からなる配列 arr[] が与えられます。求めるのは、同じ配列内に存在する各要素のフロア（下限値）です。フロアとなる要素が見つかればその値を出力し、存在しない場合は -1 を出力します。配列における要素のフロアとは？配列内のある要素のフロアとは、その要素以下の値を持つ要素の中で、最も近い（最大の）要素のことを指します。具体例で理解しよう入力: arr[] = {3, 1, 5, 7, 8, 2} 出力: 2 -1 3 5 7 1この例では、要素 3 のフロアは 2、要素 1 以下の要素は他に存在しないため -1、要素 5 のフロアは 3、というように各要素ごとに計算してい

この問題では、N個の数値からなる配列arr[]と整数xが与えられます。求められているのは、バイナリリフティング（Binary Lifting）を使用して、N個の数値の累積和（プレフィックスサム）の中からX以上となる最初の要素を見つけるプログラムを作成することです。配列の累積和（Prefix Sum）とは、元の配列の先頭から各インデックスまでの要素の合計を、その位置の値とする配列のことです。例：array[] = {5, 2, 9, 4, 1}prefixSumArray[] = {5, 7, 16, 20, 21}問題を理解するための例入力：arr[] = {5, 2, 9, 4, 1}, X

この問題では、N個の整数からなる配列 arr[] とサイズkのウィンドウが与えられます。求めるのは、サイズkの各ウィンドウに含まれる最初の負の整数を見つけるプログラムです。負の数が存在する場合はその値を出力し、存在しない場合は「0」を出力して負の数がないことを示します。問題の例具体的な入力と出力を見て、問題を理解しましょう。入力：arr[] = {-2, 2, -1, 4, 3, -6}, k = 2出力：-2, -1, -1, 0, -6解説：ウィンドウサイズ k = 2 の場合、{-2, 2} → 最初の負の数は -2{2, -1} → 最初の負の数は -1{-1, 4} → 最初の負の数

この問題では、サイズNのリンクリストLLが与えられます。求められているのは、リンクリスト内で最初に一度だけ出現する要素（非重複要素）を見つけるプログラムを作成することです。リンクリストとは、データ構造同士をポインタ（リンク）で順番につなげた一連のデータ構造です。問題の例具体例を使って問題を確認してみましょう。入力：LL = 4 => 6 => 2 => 4 => 1 => 2 => 6 => 5出力：1解説：このリンクリストでは、一度だけ出現する要素は「1」と「5」です。そのうち、リンクリストの先頭に近い方に出現しているのは「1」なので、答えは1となり

この問題では、サイズNの文字列配列 str[] が与えられます。求められるのは、「配列内にその逆順の文字列も存在するような、最初の文字列を見つけるプログラムを作成すること」です。問題の例具体例を使って問題を確認してみましょう。入力: str[] = [python, program, C#, language, #C] 出力: C#この例では、「C#」を逆順にした「#C」が同じ配列内に存在するため、「C#」が答えとなります。解法アプローチ1：全探索（総当たり法）最もシンプルな解き方は、文字列配列の各要素を順番に走査し、残りの要素の中にその文字列の逆順が存在するかどうかをチェックする方法です。逆

問題概要この問題では、サイズNの文字列str[]と整数Xが与えられます。求められているのは、文字列から最初のX個の母音を出力するプログラムを作成することです。文字列から見つかった最初のX個の母音を出力し、母音がX個未満しか存在しない場合は-1を出力します。具体例を使って問題を理解しましょう。入力: str = learn C programming language, X = 5 出力: e, a, o, a, i 母音とは a, e, i, o, u のことです解決アプローチこの問題に対するシンプルな解決策は、文字列を1文字ずつ先頭から走査する方法です。走査の過程で見つけたすべての母音を、結

この問題では、整数値Nが与えられ、N番目の偶数フィボナッチ数を求めることが課題となります。フィボナッチ数列は、直前の2つの数を加えることで次の数を生成していく数列です。数列はF0とF1という2つの初期値から始まり、初期値には (0, 1) または (1, 1) が用いられます。問題の確認まず、具体例を使って問題を理解しましょう。入力 : N = 4 出力 : 144解法アプローチこの問題を解くためのシンプルな方法は、「フィボナッチ数列において3つごとの数が必ず偶数になる」という性質を利用することです。さらに、偶数のみを並べた数列も漸化式に従うという点がポイントです。偶数フィボナッチ数列の漸化式

問題の概要この問題では、0と1のみで構成される2次元のバイナリ行列が与えられます。私たちのタスクは、DFS（深さ優先探索）を用いて、その行列の中にいくつの「島」が存在するかを求めることです。ここでいう島とは、行列の中で上下左右だけでなく斜め方向にも隣接している、1つ以上の「1」の集まりのことを指します。具体例で問題を理解しよう入力 : bin[][] = {{ 1 0 0 0}   {0 1 0 1}   {0 0 0 0}   {0 0 1 0}} 出力 : 3説明：この行列には以下の3つの島が存在します。bin00 と bin11

問題の概要 この問題では、2次元のバイナリ行列（0と1だけで構成されたマトリックス）が与えられます。私たちのタスクは、素集合データ構造（Union-Find）を使って島の数を求めることです。 ここでいう「島」とは、行列の中で縦・横・斜めのいずれかの方向に隣接している1つ以上の「1」から構成される領域のことを指します。 具体例で理解する 入力： bin[][] = {{ 1 0 0 0}    {0 1 0 1}    {0 0 0 0}    {0 0 1 0}} 出力： 3 解説： 島は以下の3つ：    bi

この問題では、3つの整数 A、B、C が与えられます。私たちの課題は、与えられた方程式を満たす解の個数を求めることです。 対象となる方程式 X = B*Sm(X)^A + C ここで、Sm(X) は X の各桁の数字を合計した値（桁和）を表します。 つまり、1 以上 109 以下の範囲に存在する整数の中から、上記の方程式を満たすすべての X の値を数える必要があります。 具体例を見て、問題を理解しましょう。 入力: A = 3, B = 6, C = 4 出力: 3 解法のアプローチ この問題を効率よく解く鍵となるのが「桁和」です。X の最大値は 999999999（9が9個）なので、桁和の最

問題概要 この問題では、階段の建設に使えるレンガの数を表す整数 N が与えられ、そのレンガで何段の階段を作れるかを求めます。 階段は与えられたレンガを使って下から順に組み上げていきます。各段は直前の段より1個多くのレンガを必要とし、最初の段は2個のレンガで作られます。つまり、1段目＝2個、2段目＝3個、3段目＝4個という具合です。残りのレンガが次の段を積むのに足りなくなった時点で構築を終え、それまでに完成した段数が答えとなります。 入出力例 入力 N = 40 出力 7 動作の解説 N = 40 のとき、段を積むごとにレンガの消費数と残数は次のように変化します。 段必要レンガ数累計使用数残

この問題では、0と1のみで構成されるバイナリ配列 bin[] が与えられ、その中に含まれる0の個数を求めることが課題となります。 配列はソート済みであり、すべての1が先頭に、すべての0が後ろにまとめて配置されています。つまり、最初の0が現れる位置が分かれば、残りの要素はすべて0であるため、簡単に個数を計算できます。 問題の例 入力: arr[] = {1, 1, 1, 0, 0, 0, 0} 出力: 4 この例では、配列の後半に0が4つ連続しているため、答えは「4」となります。 解決アプローチ この問題を解く鍵となるのは「配列がソート済みである」という性質です。配列内で最初に0が出現するイン

問題概要 この問題では、小文字の英字のみで構成された入力文字列が与えられ、その中で最も多く出現する文字(最頻出文字)を求めます。 出現回数が同じ文字が複数存在する場合は、辞書順でより小さい文字を出力する必要があります。 入出力例 入力: string = programming 出力: g 「programming」には「r」「m」「g」がそれぞれ2回ずつ登場しますが、辞書順で最小の「g」が答えとなります。 解決アプローチ この問題はハッシュ法(ハッシュテーブル)を使うことで効率的に解けます。文字列を走査しながら各文字の出現回数を配列に記録し、最終的に最大の出現回数を持つ文字を特定します。この

この問題では、サイズ n の配列 arr[] が与えられ、範囲内で欠落している1つの数値を見つけることが求められます。 配列には、最小値から(最小値 + n)までの連続する整数がすべて含まれていますが、そのうち1つだけが欠落しています。私たちのタスクは、この欠落した数値を特定することです。 具体例で問題を確認してみましょう。 入力: arr[] = {4, 8, 5, 7} 出力: 6 解決アプローチ 方法1: ソートを利用した単純な解法 最も基本的な解決策は、配列をソートした後、最小値から始まる範囲の要素を順番に確認し、範囲内に存在するはずなのに配列に現れない最初の要素を探す方法です。 た

本記事では、サイズnの整数型配列arr[]が与えられたとき、その中に一つだけ存在する「異なる要素」を見つける問題を、C++で解く方法を解説します。 配列には2種類の値しか含まれておらず、ひとつを除いたすべての要素が同一の値を持っています。その「仲間はずれ」の要素を効率よく特定することが目標です。 問題例 具体的な入出力の例を見てみましょう。 入力: arr[] = {1, 1, 1, 2, 1, 1, 1, 1} 出力: 2 この例では、ほとんどの要素が「1」であるのに対し、「2」だけが異なるため、答えは2となります。 解法アプローチ 1. 全探索による単純なアプローチ(O(N²)) 最も直感

問題概要 この問題では、サイズnの配列arr[]と2つの整数a、bが与えられます。求めるのは、配列内でちょうどb回出現する唯一の要素です。 配列内のすべての値はa回出現しますが、ただ1つの値だけがb回出現します。私たちのタスクは、この特別な値を見つけることです。 問題例 具体例を使って問題を理解しましょう。 入力: arr[] = {3, 3, 3, 3, 5, 5, 5, 1, 1, 1, 1}、a = 4、b = 3 出力: 5 この例では、3は4回、1は4回出現していますが、5だけが3回(b回)出現しているため、答えは5となります。 解決アプローチ 方法1: 単純なカウント方式(O(

この問題では、1からNまでの値が格納され、そのうち1つの値だけが欠落しているサイズNの配列 arr[] が与えられます。私たちのタスクは、ソートされた配列の中で欠落している唯一の数値を見つけることです。具体例で問題を確認してみましょう。入力:arr[] = {1, 2, 3, 5, 6, 7}出力:4上記の例では、配列には1〜7の値が含まれるはずですが、4が欠落しているため、出力は4となります。解法1: 線形探索によるアプローチ最もシンプルな解決策は、ソートされた配列を先頭から順番に走査する方法です。「i番目の要素は i + 1 になるはず」という性質（arr[i] = i + 1）を利用して

問題概要この問題では、1からN-1までの値が格納されたサイズNの配列arr[]が与えられます。ただし、そのうち1つの値だけが2回出現しています。私たちのタスクは、サイズnのソート済み配列の中で唯一繰り返されている要素を見つけることです。具体例で問題を確認しましょう。入力：arr[] = {1, 2, 3, 4, 5, 5, 6, 7}出力：5解法アプローチ1：線形探索（O(N)）最もシンプルな解き方は、線形探索を用いる方法です。配列を先頭から順に走査しながら、隣接する要素arr[i]とarr[i+1]の値を比較します。両者が一致した場合、その値が重複している要素となるため、arr[i]を返しま