C++

問題概要この問題では、整数 N が与えられます。求めるのは、級数 1 + 22 + 333 + 4444 + 55555… の初項から第 N 項までの総和です。具体例で問題を確認しましょう。入力: N = 4出力: 4800解説:1 + 22 + 333 + 4444 = 4800解法のアプローチ最も単純な解法は、級数の一般項を順に生成しながら第 n 項まで足し合わせることですが、この方法では O(n) の時間がかかります。そこで、級数の総和を閉じた形の公式として導出すれば、O(1) の定数時間で答えを計算できます。一般項の導出対象となる級数は次の通りです。1 + 22 + 333 + 444

問題概要この問題では、「M」と「F」の2種類の文字のみで構成される文字列と、時間 t が与えられます。指定された時刻におけるキュー（待ち行列）の並びを求めることが課題です。この文字列は、バスに乗り込むために一列に並んだ人々を表しています。列の中の男性はみな紳士的で、自分の後ろに女性が並んでいることに気づくと、すぐにその女性と順番を交換します。バスの発車まであと t 単位時間があり、1回の交換につき1単位時間がかかります。つまり、バスが到着したときの列の状態をシミュレーションによって求める必要があるのです。具体例で理解しよう入力 : queue = MFMMFF , t = 3 出力 : FFM

この記事では、数値nが与えられたときに最初のN個の自然数の平均を求める方法について解説します。平均とは、すべての数値の合計をその個数で割った値として定義されます。つまり、最初のN個の自然数の平均は、「1からNまでの自然数の合計」を「N」で割った値ということになります。問題の例入力 : N = 23 出力 : 12説明：1 + 2 + 3 + ... + 22 + 23 = 276 276 / 23 = 12解法のアプローチ平均を求めるためには、以下の基本的な公式を使用します。Average = sum(N) / NAverage = (1 + 2 + 3 + ... + N) / Nここで、最

この記事では、二分木（バイナリツリー）が与えられたときに、その中から最も深いノードを見つける問題について解説します。 二分木と最も深いノードとは 二分木はデータの格納に用いられる特別なデータ構造で、「各ノードが持てる子ノードは最大2つまで」という条件を満たすのが特徴です。 二分木における最も深いノードとは、木の中で最大の高さ（深さ）に位置するノードのことを指します。 具体例で理解しよう 入力： 出力： 8 この例では、ノード8が最も深い位置にあるため、答えは8となります。 解法アプローチ この問題には複数の解き方がありますが、基本となる考え方は共通しています。「木の高さを求め、その高さにあ

この問題では、直角三角形の斜辺（H）と面積（A）の2つの値が与えられ、そこから直角三角形の各辺の長さ（高さと底辺）を求めることが課題となります。直角三角形とは、2つの辺が直角（90度）で交わる特殊な三角形のことです。具体例で問題を確認しましょう：入力 : H = 7 , A = 8 出力 : 高さ = 2.43, 底辺 = 6.56解法のアプローチこの問題は、数学的な公式を用いることで解くことができます。ここで、公式を実際に導出してみましょう。まず、直角三角形の面積と三平方の定理（ピタゴラスの定理）から、次の2つの式が成り立ちます。A = (1/2) × h × bH² = h² + b²ここ

問題の概要 この問題では、スペースで区切られた複数の単語を含む文字列 str が与えられます。私たちのタスクは、文字列の中から最初に見つかる、最も長い偶数長の単語を検索することです。 言い換えると、長さが最大で、かつ文字数が偶数になっている単語(スペースとスペースの間にある文字列)を抜き出す必要があります。 具体例で問題を確認してみましょう。 Input : str = "learn programming at TutorialsPoint" Output : TutorialsPoint 説明 − 偶数の長さを持つ単語は「TutorialsPoint」です。 解決アプロ

この問題では、スペースで区切られた複数の単語からなる文字列 str が与えられます。私たちのタスクは、文字列の中で最初に繰り返し出現する単語を見つけることです。つまり、「2つのスペースに挟まれた単語」の中から、文字列内で重複して現れる最初のものを特定する必要があります。問題を理解するための例入力 : str = C program are easy to program 出力 : program解決アプローチこの問題に対するシンプルな解決策は、ハッシュマップ（unordered_map）というデータ構造を利用することです。まず、文字列を単語ごとに分割しながら読み込み、各単語とその出現回数をハッ

問題の概要この問題では、n個の整数値を含む配列arrが与えられます。私たちの課題は、整数配列の中から最初の繰り返し要素を見つけることです。具体的には、配列内で2回以上出現している整数値のうち、最も早い位置(インデックス)に出現するものを特定する必要があります。例で理解しましょう入力 : arr[] = {4, 1, 8, 9, 7, 2, 1, 6, 4}出力 : 4説明 −複数回出現している整数は「4」と「1」です。4の最初の出現位置は1よりも前のため、答えは4となります。解法アプローチ1:二重ループを使う単純な方法最もシンプルな解決策は、ネストされたループ(二重ループ)を使用することです。

この問題では、整数値 N が与えられ、最初のN個の自然数の「良い順列(good permutation)」を見つけることが課題となります。順列とは、あるオブジェクトの集合の全部または一部を、並べる順序を考慮して並べたもののことです。良い順列とは、1 ≤ i ≤ N を満たすすべての i について、次の条件を満たす順列を指します。P[P[i]] = iつまり、順列を2回適用すると元の値に戻るという性質(自己逆順列)を持つ必要があります。例で問題を理解する入力 : N = 1出力 : -1N = 1 の場合、条件を満たす順列が存在しないため、-1 を出力します。解法アプローチこの問題に対するシンプ

この記事では、直角三角形の「高さ H」と「底辺 B」にあたる2つの整数値が与えられたとき、その斜辺を求める方法をC++で解説します。 直角三角形とは、1つの内角が直角（90度）となっている特別な三角形のことです。 まず、具体的な例で問題を確認してみましょう。 入力：B = 5, H = 12 出力：13.00 解法のアプローチ この問題は、ピタゴラスの定理（三平方の定理）を使うことでシンプルに解くことができます。 ピタゴラスの定理とは、「直角三角形の斜辺の2乗は、残りの2辺の2乗の和に等しい」という定理です。 数式で表すと次のようになります。 $H^2\:=\:h^2\:+\:b^2$ つま

この問題では、ブール値（0と1のみ）で構成され、昇順にソートされた配列 bin[] が与えられます。求められるのは、配列内で最初に現れる「1」のインデックスを見つけることです。問題の例入力 : bin[] = {0, 0, 0, 1, 1} 出力 : 3説明： ソート済みバイナリ配列の中で、最初に「1」が出現するのはインデックス3の位置です。解法アプローチ1：線形探索（Linear Search）最もシンプルな方法は線形探索です。配列を先頭（インデックス0）から末尾まで順番に走査し、「1」が最初に見つかった時点でそのインデックスを返します。もし配列内に「1」が存在しない場合は -1 を返します

問題概要この問題では、ブール値（0と1のみ）がソートされた順序で格納された無限配列 bin[] が与えられます。私たちのタスクは、この無限ソート済み配列の中で最初の1が出現するインデックスを見つけることです。ここでいう「無限配列」とは、配列の長さに上限がなく、かつ配列内に必ず1が存在することが保証されているという意味です。問題を理解するための例入力 : bin[] = {0, 0, 0, 1, 1, ....} 出力 : 3説明：バイナリ配列において、最初の1はインデックス3の位置に出現します。解決アプローチこの問題を解くには、配列内で最初の1が出現するインデックスを見つける必要があります。そ

この問題では、サイズNの配列arr[]が与えられ、配列内で可能な移動を行った後の左ポインタのインデックスを求めることが課題となります。配列には2つのポインタ、すなわち左ポインタと右ポインタが用意されています。左ポインタはインデックス0から開始し、値は増加していきます。右ポインタはインデックス(n-1)から開始し、値は減少していきます。ポインタの値は、通過した合計値がもう一方より小さい場合に増加します。つまり、左ポインタの合計が右ポインタの合計より小さければ左ポインタが増加し、そうでなければ右ポインタが減少します。そして合計値は更新されます。問題を理解するための例入力 : arr[] = {5,

問題の概要この問題では、サイズNの配列res[]が与えられ、範囲合計クエリ（レンジサムクエリ）を実行した後の配列から、元の初期配列を求めることが課題となります。具体的には、ある初期配列に対して[s, e, val]という形式のクエリを実行した結果、与えられた配列rel[]が得られるような、クエリ実行前の元の配列を見つける必要があります。各[s, e, val]クエリの各要素は、以下の意味を持ちます。s → 開始インデックスe → 終了インデックスval → 配列のs番目からe番目までの各要素に加算する更新値具体例で問題を理解しよう入力：rel[] = {7, 4, 8}Query[][] =

問題の概要この記事では、サイズnの整数型配列arr[]、サイズmの配列del[]、および整数kが与えられたときに、指定された要素を削除した後のk個の最大値を見つける方法を解説します。具体的には、del[]に含まれるすべての要素をarr[]から削除し、残った配列の中から大きい方からk個の要素を出力します。なお、同じ値が複数存在する場合は、先に出現したインスタンスを削除するものとします。例で理解しよう入力 : arr[] = {3, 5, 1, 7, 9, 2}, del[] = {1, 9, 3}, k = 2 出力 : 7, 5説明：要素を削除した後の配列arr[] : {5, 7, 2} 最

問題の概要この問題では、サイズnの配列arr[]、サイズmの配列del[]、そして整数kが与えられます。求められているのは、指定された要素を削除した後にk個の最小値を見つけることです。具体的には、配列arr[]からdel[]に含まれるすべての要素を削除した後の、小さい方からk個の要素を出力する必要があります。同じ値が複数存在する場合は、最初に出現したインスタンスを削除するものとします。例を使って問題を理解しましょう。入力 : arr[] = {3, 5, 1, 7, 9, 2}, del[] = {1, 9, 3}, k = 2 出力 : 2, 5説明 −del[]の要素を削除した後の配列ar

問題概要この問題では、2つの整数値 N と k が与えられ、自然数 N の k 番目に小さい約数を求めることが課題となります。具体例を見てみましょう。入力 : N = 15, k = 3出力 : 5解説 −15 の約数は 1, 3, 5, 153番目に小さいのは 5解法アプローチ①：約数を列挙してソートする方法最もシンプルな解法は、N の約数をすべて求め、ソートした状態で保存したうえで、k 番目の値を出力することです。手順は次のとおりです。1 から √N までループし、i が N を割り切れるかどうかを判定する割り切れる場合、i と N/i はペアの約数なので、両方を配列に格納する配列を昇順に

問題の概要この問題では、区間 L〜R を持つ整数の範囲が N 個、二次元配列 range[N][2] として与えられ、さらに整数値 k が渡されます。求めるのは、与えられた N 個の範囲から生成される数列の中の k 番目の要素です。具体例で問題を確認してみましょう。入力 : ranges[][] = {{1, 3}, {5, 7}}, k = 4 出力 : 5説明:生成される数列は {1, 2, 3, 5, 6, 7} 4番目の要素は 5 になります。解法①:配列に全要素を構築するシンプルな方法もっとも直感的な解決方法は、指定された範囲に含まれるすべての整数を順に配列へ格納していき、その配列の

問題の概要 この記事では、サイズNの木と、木内の頂点V、整数kが与えられたときに、頂点Vを根とする部分木のDFS(深さ優先探索)順においてk番目に訪問されるノードを求める方法を解説します。 つまり、頂点VからDFS探索を開始したときにk番目に現れるノードを求め、そのようなノードが存在しない場合は-1を返します。 入力例 次のような木を考えます(根は頂点5)。 5 / | \ \ 8 2 10 3 / \ \ 6 1 9

問題概要 サイズnの整数型配列arr[]と、削除したい要素を格納したサイズmの配列del[]が与えられます。求めたいのは、arr[]からdel[]に含まれる要素をすべて取り除いた後に残る、最大の要素の値です。 なお、削除対象の要素が配列内に複数存在する場合でも、削除するのは最初に出現した1つだけである点に注意してください。 入出力例 入力 : arr[] = {3, 5, 1, 7, 9, 2}, del[] = {1, 9, 3} 出力 : 7 解説: 要素を削除した後の配列 arr[] : {5, 7, 2} この配列の最大値は 7 解法1: ソートを利用するシンプルなアプローチ 最も分か