C++

問題概要nums という整数型の配列が与えられ、サイズ k のスライディングウィンドウが配列の左端から右端へ向かって移動していくとします。ウィンドウの中からは常に k 個の数値だけが見えており、ウィンドウは毎回 1 つずつ右に移動します。このとき、各位置におけるウィンドウ内の最大値を順番に求めるのが本問題です。例として、入力が [1,3,-1,-3,5,3,6,8]、k = 3 の場合を考えてみましょう。ウィンドウの動きとそれぞれの最大値は次の表のようになります。ウィンドウの位置最大値13-1-35368313-1-35368313-1-35368313-1-35368513-1-353686

問題概要0から9までの数字のみで構成された文字列と、1つの目標値が与えられます。数字の間に二項演算子「+」「-」「*」を挿入し、その式の評価結果が目標値と一致するような、考えられるすべての組み合わせを求めて返すのがこの問題です。例えば、入力が「232」で目標値が8の場合、答えは [2*3+2, 2+3*2] となります。アルゴリズムの流れこの問題はバックトラッキング（深さ優先探索）を使って解きます。以下の手順に従います。solve() というメソッドを定義します。引数は idx（現在のインデックス）、s（元の数字列）、curr（現在の計算結果）、target（目標値）、temp（構築中の式文字

データストリームに対して、要素が次々と追加されていく状況を考えてみましょう。このようなストリームから、その時点までに追加されたすべての数値の中央値(メディアン)を常に効率よく取得できるシステムを実装する必要があります。中央値とは、ソート済みのリストの中央に位置する値のことです。リストの長さが奇数の場合は中央の要素がそのまま中央値となり、偶数の場合は中央の2つの要素の平均を取ります。この問題を解くために、次の2つのメソッドを実装します。addNum(): ストリームに数値を1つ追加するfindMedian(): それまでに追加されたすべての数値の中央値を返すアルゴリズム(解法の手順)この問題は、

問題概要n個の風船があり、それぞれに0からn-1までのインデックスが振られています。各風船には配列 nums で表される数字が書かれており、すべての風船を割ることが目標です。風船 i を割ると、nums[i-1] × nums[i] × nums[i+1] の積に相当する枚数のコインを獲得できます。風船を割った後は、その左右にあった風船 i-1 と i+1 が隣接します。賢い順序で風船を割り、獲得できるコインの合計を最大化しましょう。例えば、入力が [3, 1, 5, 7] の場合、答えは 148 になります。まず配列は [3, 1, 5, 7] の状態から始まります。最初に 1 を割ると 3

問題の概要配列 nums が与えられたとき、count[i] に「nums[i] より右側に存在する小さい要素の個数」を格納した配列 count を求める問題を考えてみましょう。例えば、入力が [5,2,7,1] の場合、結果は [2,1,1,0] となります。この問題は、Binary Indexed Tree(BIT・フェニック木)を使うことで効率的に解くことができます。単純な二重ループでは O(n²) の計算量が必要になりますが、BIT を利用すれば O(n log m)(m は値の範囲)まで削減できます。アルゴリズムの手順update() というメソッドを定義します。引数はインデックス、

問題概要小文字の英字のみで構成された文字列 s が与えられます。この文字列から重複する文字をすべて取り除き、各文字がちょうど1回だけ出現するようにします。そのうえで、結果の文字列が辞書順で最小になるようにしなければなりません。例えば、入力が「abccb」であれば、出力は「abc」となります。アルゴリズムの考え方この問題は、貪欲法（グリーディ法）とスタックを組み合わせることで効率的に解くことができます。ポイントは次の2つです。各文字が「今後まだ出現するか」を出現回数として管理することすでにスタックに積んだ文字でも、後で再び出現できるなら、より小さい文字のために取り除けること処理の手順答えを格納す

問題の概要配列 nums と整数 n が与えられたとします。配列に要素を追加（パッチ）することで、範囲 [1, n]（両端を含む）内の任意の整数が、配列内のいくつかの要素の総和として表せるようにしたいと考えます。このとき、必要な追加要素（パッチ）の最小個数を求めるのが本問題です。たとえば、配列が [1, 4]、n = 7 の場合、答えは 1 になります。初期状態では、部分集合の和として 1、4、5 しか作れません。しかし 2 を配列に追加すると、部分集合は [1]、[2]、[4]、[1,2]、[1,4]、[2,4]、[1,2,4] となり、その総和は順に 1、2、4、3、5、6、7 となって、

問題の概要n個の数値からなる配列 x があるとします。点 (0, 0) を出発点として、まず x[0] 単位だけ北へ移動し、続いて x[1] 単位だけ西へ、x[2] 単位だけ南へ、x[3] 単位だけ東へ……というように移動を繰り返します。つまり、1回移動するごとに進行方向は反時計回りに90度変化していきます。このとき、追加の記憶領域を O(1) しか使わないワンパス（1回の走査）アルゴリズムを設計し、描かれる経路が自分自身と交差するかどうかを判定してください。例えば、配列が [3, 4, 2, 5] の場合は次のようになります。この場合、経路は自分自身と交差するため、答えは true になりま

整数からなるデータストリーム a1, a2, ..., an, ... が順番に入力される状況を想定しましょう。この問題では、それまでに入力されたすべての数値を、互いに重なり合わない「互いに素な区間」のリストとして要約する必要があります。 たとえば、入力される整数が 1, 3, 8, 2, 7, ... である場合、各時点での要約結果は以下のように変化していきます。 [1, 1] [1, 1], [3, 3] [1, 1], [3, 3], [8, 8] [1, 3], [8, 8](2 が追加され、[1,1] と [3,3] が連結される) [1, 3], [7, 8](7 が追加され、[

この記事では、整数 n が与えられたときに、n番目のスターナンバー を求めるC++プログラムの作成方法を解説します。スターナンバーとは？スターナンバー（Star Number）とは、中心に点を置き、その周囲に六芒星（六角星）の形を描いたときの点の総数を表す特殊な数です。図形的には「中心付き六芒星数」と呼ばれることもあります。スターナンバーの例は以下の通りです。1, 13, 37, 73, 121, ...問題の理解具体的な入力と出力の例を見てみましょう。入力n = 5出力121n = 5 のとき、5番目のスターナンバーである 121 が出力されます。解法のアプローチn番目のスターナンバーは、次

この問題では、指定された級数に対応する2つの値 x と n が与えられます。私たちの課題は、C++で級数「1 + x/2! + x²/3! + … + xⁿ/(n+1)!」の和を求めるプログラムを作成することです。問題の概要： 与えられた x と n の値をもとに、級数の総和を計算する必要があります。この級数では、i番目の項は直前の項に x/i を掛けた値になっています。具体例で問題を理解しよう入力x = 6, n = 4出力29.8解説この級数の和は以下のように計算されます。1 + 6/2! + 36/3! + 216/4! + 1296/5!= 1 + 3 + 6 + 9 + 10.8=

この記事では、2つの数値 a と n が与えられたとき、級数 a1/1! + a2/2! + a3/3! + a4/4! + ……… + an/n! の総和を求めるC++プログラムの作成方法を解説します。問題の概要与えられた a と n の値をもとに、上記の級数の総和を計算することが課題です。この級数は特殊な構造を持っており、各項は「直前の項に a/i を掛けた値」になっています（i は 1 から n まで）。この性質を利用すると、階乗や累乗を毎回計算する必要がなくなり、効率的な実装が可能です。入出力例で理解する入力a = 3, n = 4出力15.375説明級数の総和は以下のように計算されま

問題の概要 本記事では、n個の整数値を含む配列 arr[] が与えられたとき、その配列内のすべての要素の合計を求めるC++プログラムの作成方法を解説します。 プログラムの説明 ― 与えられた配列の全要素を順番に加算し、その合計値を返します。 まずは、具体的な例を見ながら問題を理解しましょう。 入力 arr[] = {3, 1, 7, 2, 9, 10} 出力 32 説明 Sum = 3 + 1 + 7 + 2 + 9 + 10 = 32 解法のアプローチ 配列内の要素の合計を求めるには、配列を先頭から順に走査し、各要素を1つずつ取り出しては変数 sumVal に加算していきます。走査が完了した

このチュートリアルでは、C++を使って最初のn個の自然数の合計を求める方法について解説します。整数nが与えられたとき、1からnまでの自然数をすべて足し合わせ、その合計を計算して出力するのが今回のタスクです。サンプルコード#include<iostream> using namespace std; //最初のn個の自然数の合計を返す関数 int findSum(int n) { int sum = 0; for (int x=1; x<=n; x++) sum = sum + x; return sum; } int main() {

この問題では、数列を定義する2つの整数 n と k が与えられます。私たちのタスクは、C++ を使って次の形式で表される数列の総和を求めるプログラムを作成することです。 (1×2×3×…×k) + (2×3×…×k×(k+1)) + (3×4×…×(k+1)×(k+2)) + … + ((n−k+1)×(n−k+2)×…×n) 各項は「連続する k 個の整数の積」で構成されており、隣接する項どうしは開始位置が1つずつずれていきます。ここでは、与えられた k の値に基づいて、この数列の総和を計算します。 入力例と出力例 入力 n = 4, k = 3 出力 30 説明 数列：(1×2×3)

この記事では、3つの値 a（初項）、d（公差）、n（項数）が与えられたときに、C++を使って調和級数の総和を求めるプログラムの作成方法を解説します。 調和級数とは？ 調和数列（Harmonic Progression：HP）とは、各項の逆数をとると等差数列になる数列のことです。つまり、調和数列 A1, A2, A3…An の各項の逆数 1/A1, 1/A2, 1/A3 が等差数列を構成します。 したがって、一般的な調和数列は次のように表せます。 1/a, 1/(a+d), 1/(a+2d), … 1/(a + nd) ここで、1/a が初項、d は対応する等差数列の公差です。 問題の概

この問題では、ある数値 n が与えられます。私たちのタスクは、「1から n までの素数の合計を求めるC++プログラム」を作成することです。素数とは、約数が「1」と「その数自身」の2つしか存在しない数のことです。たとえば、2、3、5、7 などが素数にあたります。例を使って問題を理解しましょう。入力n = 15出力41説明1から15までの素数は、2, 3, 5, 7, 11, 13 の6つです。これらをすべて足し合わせると、合計は 41 になります。解法1：ループで素数を判定するシンプルな方法最も基本的な解き方は、2から n までの各数値について「その数が素数かどうか」を順番に判定し、素数であれば

この問題では、数値 n が与えられます。私たちのタスクは、C++で級数 1 + 1/2 + 1/3 + 1/4 + … + 1/n の合計を求めるプログラムを作成することです。コードの説明ここでは、級数 1 + 1/2 + 1/3 + 1/4 + … + 1/n の第 n 項までの合計を求めます。この級数は「調和級数」と呼ばれるものです。調和数列(Harmonic Progression)とは、各項の逆数を並べると等差数列になる性質を持つ数列のことです。つまり、調和数列 A1, A2, A3, …, An に対して、その逆数である 1/A1, 1/A2, 1/A3, … が等差数列を構成します

問題概要 この問題では、級数の第n項を表す整数nが与えられます。私たちの課題は、C++で級数 1 + 2 + 2 + 3 + 3 + 3 + … + n の総和を求めるプログラムを作成することです。 問題の説明 ― この級数では、第k項が「数kをk回加えた値」になっています。言い換えると、これは平方数（1×1、2×2、3×3…）を順番に加えていく級数です。 入出力例 まず、具体例で問題を確認しましょう。 入力： n = 4 出力： 30 説明： 第4項までの総和は 1 + 2 + 2 + 3 + 3 + 3 + 4 + 4 + 4 + 4 = 30 となります。 解法アプローチ 最も効率的な解

問題の概要 本記事では、級数の第n項を指定する整数nが与えられたとき、C++で次の級数の総和を求めるプログラムを作成します。 1×2×3 + 2×3×4 + 3×4×5 + … + n×(n+1)×(n+2) 問題の説明：与えられた級数について、第n項までの和を求めます。これは「i×(i+1)×(i+2)」という形の項を、i = 1 から n まで順番に足し合わせることに相当します。 入出力例で問題を理解しよう 入力： n = 5 出力： 420 説明： 1×2×3 + 2×3×4 + 3×4×5 + 4×5×6 + 5×6×7= 6 + 24 + 60 + 120 + 210 = 420