C++

同じ長さの2つの数値リスト「performance（業績）」と「costs（希望額）」、そして整数 k が与えられているとします。各従業員 i は performance[i] のレベルで業務を行い、少なくとも costs[i] の報酬を求めています。このとき、k 人の従業員を雇用するための最小コストを求めるのが課題です。ただし、採用された従業員は、グループ内の他のメンバーと比較した業績に比例して支払われるという条件が付きます。たとえば、入力が performance = [5, 3, 2]、costs = [100, 5, 4]、k = 2 の場合、出力は 10 になります。従業員1と従業員

この記事では、C++を使って「周波数スタック（FrequencyStack）」と呼ばれる特殊なスタックを構築する方法を解説します。周波数スタックは、以下の2つの操作をサポートするデータ構造です。 append(x)：値 x をスタックに追加（プッシュ）します。 pop()：スタック内で最も出現頻度の高い要素を取り除き、その値を返します。同じ頻度の要素が複数存在する場合は、スタックのトップに最も近い要素が取り除かれて返されます。 例えば、7, 9, 7, 9, 6, 7 の順で要素を追加し、その後 pop() を4回呼び出すと、出力はそれぞれ 7, 9, 7, 6 となります。 アルゴリズム

問題の概要 数値のリスト nums が与えられ、その中の任意の部分リスト(連続する区間)を最大1回だけ反転できるものとします。この操作を行った後、次の式で表される「隣接要素の絶対差の合計」が取り得る最大値を求めます。 Σi=0n−2 |nums[i+1] − nums[i]| 例えば、入力が nums = [2, 4, 6] の場合を考えてみましょう。部分リスト [4, 6] を反転すると、リストは [2, 6, 4] になります。このとき |2 − 6| + |6 − 4| = 4 + 2 = 6 となるため、出力は 6 です。 解法のアプローチ すべての反転候補を素朴に試すと計算量が

問題概要 最大スタックとは、通常のスタック操作に加えて「現在の最大値の取得」や「最大値の削除」を効率よく行えるデータ構造です。ここでは、以下の操作をすべてサポートする最大スタックをC++で実装します。 MaxStk()：最大スタックの新しいインスタンスを構築する push(val)：値 val をスタックに挿入する top()：スタックの最上位にある要素を取得する max()：スタック内の最大要素を取得する pop()：最上位の要素を取り除き、その値を返す popmax()：最大要素を取り除き、その値を返す たとえば、MaxStk() でスタックを生成した後、5、15、10 の順に pus

問題概要 整数 n が与えられたとき、「n 以下の正の整数の中で、少なくとも1つの桁が2回以上現れる数」の個数を求めます。 例えば n = 200 の場合、答えは 38 になります。実際には、11・22・…・99 のような2桁の数が9個、100〜199 の範囲で同じ数字を含むものが28個、さらに 200 自身(0が2つ含まれる)の合計38個となるためです。 解法の考え方:補集合を利用した数え上げ 「重複した桁を持つ数」を直接数えるのは複雑ですが、その補集合、つまり「すべての桁が互いに異なる数」の個数を数えて全体から引けば、簡単に求められます。 答え = n −(n 以下の、全桁が異なる正整数

ここでは、MedianClass というクラスを実装することを考えます。このクラスには、次の2つのメソッドを持たせます。 add(value)：データ構造に新しい値を追加します。 median()：現在データ構造に格納されているすべての数値の中央値を求めます。 例えば、5、3、8 の順に値を追加した後で中央値を取得すると、出力は 5.0 になります。その後、さらに 9 を追加して中央値を取得すると、出力は 6.5 になります。 解き方のアプローチ この問題は、2つの優先度付きキュー（ヒープ）を組み合わせることで効率的に解けます。片方のヒープには小さい方半分の値を、もう片方には大きい方半分の

はじめに このチュートリアルでは、最小公倍数(LCM)の概念を応用したプログラムを作成します。タイトルのとおり、与えられた数 N 以下の整数の中から3つの数を選び、その LCM が最大になる組み合わせを求めるのが目的です。 まずは例から見ていきましょう。本題に入る前に、LCM とは何かを確認し、2つの数の LCM を求めるプログラムを書いてみます。 LCM(最小公倍数)とは LCM(Least Common Multiple:最小公倍数)とは、複数の数に共通する倍数のうち最も小さいものを指します。正の整数 a と b に対して、LCM は a でも b でも割り切れる最小の整数です。 また、2

はじめに このチュートリアルでは、文字列内のすべての位置に信号が到達するまでにかかる時間を計算するプログラムを作成します。まず、具体例を使って問題を説明しましょう。 扱う文字列には s と p の2種類の文字のみが含まれています。s は信号(signal)を、p は文字列内の位置(position)を表します。信号は s の地点から発生し、左右の両方向へ同時に伝わっていきます。隣の位置へ移動するのに1単位の時間がかかるものとします。私たちの課題は、すべての位置(p)を信号(s)に変換するために必要な時間を求めることです。 入出力例 入力: pppppspss → 出力: 5(先頭の5つのp

このチュートリアルでは、与えられた文字列の中から重複のない年（ユニークな年）を検出し、その総数を求めるC++プログラムを作成します。日付の形式は DD/MM/YYYY を前提とします。問題の例まず、具体的な例を見てみましょう。入力： 「01/11/2020、02/12/2020、03/10/2019」という日付を含むサンプルテキスト出力： 2このテキストには「2020」と「2019」という2つの異なる年が含まれているため、出力は 2 となります。解決のアプローチ文字列から日付を抽出するには、正規表現（regex）を使用します。C++の正規表現に不慣れな方は、まず基礎的なチュートリアルを確認して

このチュートリアルでは、行優先(row-major)と列優先(column-major)の2つの行列を加算して得られる行列のトレース(対角成分の総和)を求めるC++プログラムを作成します。 行優先行列と列優先行列の作り方 まず、行列の次数が与えられたとき、それぞれの行列がどのように構成されるのかを確認しましょう。 次数: 3 × 3 行優先行列: 123 456 789 列優先行列: 147 258 369 2つの行列が用意できたら、それらを要素ごとに加算します。そして、その結果として得られる行列のトレースこそが、私たちが求める答えです。 解決の手順 問題を解くために、次の4つ

はじめに このチュートリアルでは、与えられた積(掛け算の結果)となる2つの異なる素数を見つけるC++プログラムを作成します。まず、具体例を見てみましょう。 入力: 21 出力: 3 7 積が21になる素数の組み合わせは「3と7」です。この問題を効率よく解くには、与えられた数より小さいすべての素数を事前に求めておくのがポイントです。素数表さえあれば、あとは組み合わせを確認するだけでペアを発見できます。 アルゴリズムの手順 以下の手順に従って問題を解いていきます。 積となる数値nと、範囲内の各数が素数かどうかを記録するbool型配列を用意します。 エラトステネスの篩を使って、n未満のすべての素数

このチュートリアルでは、x + y = n かつ x × y = n を満たす2つの数を見つけるC++プログラムを作成します。ただし、そのような数が存在しない場合もあります。その際は None を出力するようにします。それでは始めましょう。解法の考え方与えられた2つの値は、ある二次方程式の「解の和」と「解の積」に相当します。二次方程式の解と係数の関係より、判別式は n2 - 4n で表されます。この値が負( n2 - 4n < 0 )の場合、実数解は存在しないため、条件を満たす2つの数は見つかりません。判別式が0以上の場合、求める2つの数は次の式で表されます。$$\lgroup n +

このチュートリアルでは、C++を使って、与えられた2つの文字列の中から「片方にしか存在しない文字」を効率的に見つける方法を解説します。まずは具体例を見てみましょう。入力例と出力例入力string_one = tutorialspoint string_two = tutorialsworld出力d n p w上記の例では、両方の文字列に共通して含まれる文字(t、u、o、r、i、a、l、s)を除き、どちらか一方にのみ存在する文字 d、n、p、w を出力しています。解法のアプローチこの問題はハッシュ(連想配列)を使うことで効率的に解けます。2重ループで全文字同士を比較する方法よりも計算量が少なく、

このチュートリアルでは、ソートされていない2つの配列から和集合（Union）と積集合（Intersection）を求めるプログラムの書き方を解説します。まずは、具体的な入力と出力の例を見てみましょう。 入力 arr_one = [1, 2, 3, 4, 5] arr_two = [3, 4, 5, 6, 7] 出力 union: 1 2 3 4 5 6 7 intersection: 3 4 5 それでは、問題を解くための手順を順番に確認していきましょう。 和集合（Union）を求める手順 2つの配列を任意の値で初期化します。 結果を格納するための空の配列 union_result を用意

このチュートリアルでは、C++を使って「指定した数 n より小さい値のみで構成される一意なペア（ユニークペア）」をすべて見つけて出力する方法を解説します。重複のない組み合わせを効率よく列挙する基本的な考え方と、実際に動作するサンプルコードを通じて学んでいきましょう。問題のアプローチこの問題は、二重ループを使うことでシンプルに解決できます。手順は以下の通りです。対象となる数 n を初期化します。外側のループで i を 1 から n 未満まで繰り返します。内側のループで j を i + 1 から n 未満まで繰り返します。ペア (i, j) を出力します。内側のループの開始点を「i + 1」とする

このチュートリアルでは、ある整数が一意な（重複のない）自然数のn乗の和として表現できる方法の数を求めるプログラムをC++で作成します。 2つの整数 number（対象の数）と power（べき指数）が与えられます。このとき、number を重複のない自然数の n 乗の和として表現する方法が何通りあるかを求めます。具体例を見てみましょう。 入力例と出力例 入力： number = 50, power = 2 出力： 3 50 を 2乗の和で表現すると、次の3通りの方法があります。 50 = 7² + 1² = 49 + 1 50 = 6² + 3² + 2² + 1² = 36 + 9 +

はじめに このチュートリアルでは、選挙の当選者（勝者）を見つけるプログラムをC++で作成します。各候補者が獲得した票が文字列の配列として与えられ、その中から最も多く票を獲得した候補者の名前を出力します。 まずは、具体的な例を見てみましょう。 入力例 {A, B, C, B, A, C, D, D, A, B, D, B, A} 出力例 A この例では、AとBが同じ票数を獲得しています。このような場合、名前のアルファベット順に基づいて当選者を決定する必要があります。アルファベット順で先に来る「A」が当選者となります。 解決の手順 それでは、この問題を解くための手順を確認しましょう。 ダミーデー

このチュートリアルでは、配列内の一部の0（ゼロ）を1に反転したときに、連続する1の数が最大になるように、どの0を反転すべきかを見つける方法を解説します。この問題はスライディングウィンドウ（Sliding Window）と呼ばれる手法を使うことで、O(n) の計算量で効率的に解くことができます。それでは、具体的な手順を見ていきましょう。アルゴリズムの手順対象となる配列と、反転できる0の最大数（maxZeroes）を初期化します。ウィンドウの開始インデックス（start）、終了インデックス（end）、およびウィンドウの長さを初期化します。連続する1の最長部分配列の長さと、その開始インデックスを記録

このチュートリアルでは、与えられた等式を満たす ΔX の値を計算するプログラムを作成します。扱う等式は次のとおりです。(a + ΔX) / (b + ΔX) = c / d数式の導出手順この問題を解くには、少し数学的な操作が必要ですが、考え方はとてもシンプルです。交叉乗算（たすき掛け）を行い、ΔX を一方の辺にまとめます。両辺に分母を掛けます：d × (a + ΔX) = c × (b + ΔX)展開します：d·a + d·ΔX = c·b + c·ΔXΔX を左辺に、それ以外を右辺に移項します：ΔX(d − c) = b·c − a·dこれにより、ΔX の値は次の式で求まります。ΔX = (

このチュートリアルでは、配列の各要素で割った余り(剰余)がすべて等しくなるような数kを見つけるプログラムを作成します。まずは具体例から見ていきましょう。 入力: arr = {10, 4, 2} 出力: 1 2 解法の鍵となる剰余の性質 2つの数 x と y(x > y)を考え、その差を x - y = d とします。このとき x = y + d と表せます。 ここで、x % k = y % k を満たす数 k が存在すると仮定し、この関係式に k を法とする剰余演算を適用すると、d に関する重要な性質が導かれます。 x % k = (y + d) % k (y + d) % k =