C++

正整数 n が与えられたとき、その値を完全平方数（1、4、9、16…など）の和として表現するために必要な「最小の個数」を求める問題を考えてみましょう。 例えば n = 13 の場合、13 = 9 + 4 と表せるため、答えは 2 となります。この記事では、この問題をC++で効率的に解くための動的計画法（DP）のアプローチを詳しく解説します。 アルゴリズムの考え方 この問題は、コイン払い戻し問題と同じ構造を持っています。「各完全平方数」をコインとみなし、金額 n を作るのに必要な最小のコイン枚数を求めるイメージです。解法の手順は以下の通りです。 長さ n + 1 のDPテーブルを作成し、すべ

この記事では、クールダウン期間ありの株式売買問題(Best Time to Buy and Sell Stock with Cooldown)をC++で解く方法を、動的計画法(DP)の考え方とともに分かりやすく解説します。 問題の概要 ある配列が与えられ、その i 番目の要素は i 日目の株価を表しているとします。このとき、利益が最大になるように売買を行うアルゴリズムを設計します。取引の回数に制限はなく、何度でも「買って売る」を繰り返せますが、次のルールを守る必要があります。 同時に複数の取引は行えない。つまり、新しい株を買う前に、必ず保有している株を売却しておかなければならない。 株を売

問題概要この問題では、正の整数で構成される配列と数値 k が与えられます。求めるのは、指定されたサイズ（k）を持つ重複しない2つの部分配列の合計の最大値です。つまり、サイズ k の互いに重ならない（異なる）2つの部分配列を選び、その合計が最大になる組み合わせを出力するプログラムを作成します。例で理解しよう入力：array = {7, 1, 6, 9, 2} , k = 2出力：{7, 1} , {6, 9}説明：サイズ2のすべての部分配列とその合計： {7, 1} : 合計 = 7+1 = 8 {1, 6} : 合計 = 1+6 = 7 {6, 9} : 合計 = 6+9 = 15 {9, 2

この記事では、与えられた配列の中から3つの要素を選んだときの合計（トリプレット和）が最大になる組み合わせを見つけるプログラムをC++で作成します。 問題の概要 配列が与えられたとき、その中から3つの要素を選び、その合計が最大となる組み合わせを求めるのが課題です。 具体例で理解しよう 入力： array = {4, 6, 1, 2} 出力： 12 解説： すべてのトリプレットの組み合わせ： (4, 6, 1) = 4 + 6 + 1 = 11 (4, 6, 2) = 4 + 6 + 2 = 12 (4, 1, 2) = 4 + 1 + 2 = 7 (6, 1, 2) = 6 + 1 + 2

この問題では、整数の配列と整数Kが与えられます。私たちの課題は、サイズKの各部分配列の中で、重複して現れない要素(一意な要素)のうち最大値を見つけるプログラムを作成することです。まず、具体的な例を使って問題を理解しましょう。入力 −array = {4, 1, 1, 3, 3} k = 3出力 −4 3 1説明 −サイズ3の部分配列を順に調べる 部分配列 {4, 1, 1} の場合、一意な要素は {4}、最大値 = 4 部分配列 {1, 1, 3} の場合、一意な要素は {3}、最大値 = 3 部分配列 {1, 3, 3} の場合、一意な要素は {1}、最大値 = 1問題を解くアプローチこの問

この問題では、1からnまでの範囲に含まれるn個の整数で構成された配列が与えられます。求めるのは、隣接する要素同士の絶対差の合計 |arr[0] − arr[1]| ＋ |arr[1] − arr[2]| ＋ … ＋ |arr[n−2] − arr[n−1]| を最大化するような並べ方における、その最大値です。問題の例具体的な例を使って問題を確認しましょう。入力： array = {1, 2, 3}出力： 3説明：最大の合計は|1−3| ＋ |2−1| = 3解き方のアプローチ最も単純な方法は、配列のすべての順列を生成し、それぞれについて絶対差の合計を計算して最大値を探すことです。しかし、順列の

この問題では、n個の整数からなる配列が与えられます。求めるのは、|arr[i] - arr[j]| + |i-j| の最大値です。つまり、配列内の任意の2つの要素について、その値の差とインデックスの差の絶対値の合計が最大になる組み合わせを見つけるプログラムを作成します。問題例具体例を使って問題を理解しましょう。入力： array = {4, 1, 2}出力： 4説明：|arr[0] - arr[1]| + |0-1| = |4-1| + |-1| = 3+1 = 4 |arr[0] - arr[2]| + |0-2| = |4-2| + |-2| = 2+2 = 4 |arr[1] - arr

この問題では、n個の要素からなる配列が与えられます。与えられた配列に対して、arr[i] % arr[j] の最大値を求めるプログラムを作成するのが課題です。つまり、配列内の2つの要素を割り算したときに生じる余りの中から、最大のものを見つける必要があります。具体例を使って問題を理解しましょう。入力 − array {3, 6, 9, 2, 1}出力 − 6説明 − 配列内のすべてのペアについて余りを計算すると、以下のようになります。3 % 3 = 0; 3 % 6 = 3; 3 % 9 = 3; 3 % 2 = 1; 3 % 1 = 06 % 3 = 0; 6 % 6 = 0; 6 % 9 =

この問題では、整数の配列が与えられます。求めるのは、配列から選んだ3つの要素（トリプレット）の組み合わせすべての中で、XOR（排他的論理和）の値が最大になるものです。 問題の例 具体的な例を使って問題を確認してみましょう。 入力： array = {5, 6, 1, 2} 出力： 6 説明： 考えられるすべてのトリプレットとそのXOR値： 5 ^ 6 ^ 1 = 2 5 ^ 6 ^ 2 = 1 5 ^ 1 ^ 2 = 6 6 ^ 1 ^ 2 = 5 この中で最も大きいXORの値は 6（5 ^ 1 ^ 2）となるため、答えは 6 になります。 解法のアプローチ 最も単純な方法は、考えられるすべて

この問題では、整数 n と、各セルの重みが格納された n × n の行列が与えられます。目的は、行列の最終行の任意の要素で終わる最大重みパスを見つけるプログラムを作成することです。経路の探索は左上のセル (0,0) から開始し、移動として許されるのは「下」と「右下（斜め）」のみです。左への移動は禁止されています。問題例具体例を使って問題を確認してみましょう。入力：n = 3 Mat[3][3] = { {4, 3, 1}, {5, 8, 9}, {6, 7, 2}}出力：19説明：取り得るすべての経路は以下の通りです。 Path1: 4+5+6 = 15 Path2:

問題の概要AとBのみで構成された文字列が与えられます。任意の文字を別の文字に切り替える(トグルする)ことで、この文字列を別の文字列へと変換できます。つまり、1つの文字列からは多数の変換パターンが考えられます。ここでの課題は、これらの変換の中で「最大の重み」を持つ変換を見つけ、その重みを求めることです。重みの計算方法文字列の重みは、以下の式で計算されます。文字列の重み = ペアの重みの合計 + 単一文字の重みの合計 − トグル(切り替え)の総数重みの計算には、以下のルールが適用されます。連続する2文字は、互いに異なる場合にのみ「ペア」として扱われます。1つのペアの重み(2文字が異なる場合)= 4

問題文 二分木が与えられたとき、その木の最大幅を求める関数を実装します。ここでいう「木の幅」とは、あるレベル（深さ）に存在するノードの数のことです。木の最大幅は、すべてのレベルの幅の中で最も大きな値となります。 以下の二分木を例に考えてみましょう。 10 / \ 7 4 / \ \ 9 2 1 / \ 2 5 この木の各レベルの幅は次のようになります。 レベル1の幅：1（ルートのみ） レベル2の幅：2（7 と 4） レベル3の幅：3（9・2・1） レベル4の幅：2

問題の概要この問題では、2つの正整数 n と k が与えられます。求めるのは、1からnまでの数値の中からk個の数を選んだ場合に得られるXOR(排他的論理和)の最大値です。例で理解しよう入力 − n = 5, k = 2出力 − 7説明 −5以下の要素は 1, 2, 3, 4, 5 すべてのXORの組み合わせ: 1^2 = 3, 1^3 = 2, 1^4 = 5, 1^5 = 4 2^3 = 4, 2^4 = 6, 2^5 = 7 3^4 = 7, 3^5 = 6 4^5 = 1 この中で最大の値は 7 です。解法のアプローチこの問題を解く鍵となるのは、XORの性質です。2つの数値のXORが最大

問題の概要範囲 [L, R] が与えられたとき、この範囲内から2つの整数を選び、そのXOR(排他的論理和)が考えられるすべての組み合わせの中で最大となるようにする問題です。例として、L = 1、R = 21 が与えられた場合を考えてみましょう。このとき出力は 31 になります。これは、15 XOR 16 = 31 となり、範囲内のどの2整数の組み合わせよりも大きなXOR値になるためです。アルゴリズムこの問題は、全組み合わせを総当たりで調べなくても、ビット演算の性質を使えば効率的に解くことができます。1. L ^ R の値を計算する 2. その値の最上位ビット(MSB)の位置を求める 3. MS

この問題では、サイズ n × n の行列が与えられます。行全体または列全体のXOR値のうち最大のものを計算するプログラムを作成するのがタスクです。 具体例を使って問題を理解しましょう。 入力 − N = 3 mat[N][N] = {{4, 9, 1}, {2, 8, 3}, {10, 12, 11}} 出力 − 13 説明 − Row1: 4^9^1 = 12 Row2: 2^8^3 = 9 Row3: 10^12^11 = 13 Col1: 4^2^10 = 12 Col2: 9^8^12 = 13 Col3: 1^3^11 = 9 この例では、すべての行と列のXORを計算し、その中で最大

この記事では、サイズ n×n の2次元配列（行列）が与えられたとき、その行列の平均値（Mean）と中央値（Median）を出力するプログラムをC++で作成します。平均値（Mean）とは平均値とは、データセット全体の平均のことです。行列の場合は、すべての要素を合計し、要素数で割ることで求められます。平均値 = （行列の全要素の合計）÷（行列の要素数）中央値（Median）とは中央値とは、データを昇順に並べ替えたときに中央に位置する要素のことです。そのため、中央値を求めるには行列の要素がソートされている必要があります。中央値は以下のように計算されます。n が奇数の場合：median = matri

この問題では、n個の整数からなる配列とm個のクエリが与えられます。各クエリで指定された範囲の平均値の整数部分（小数点以下は切り捨て）を計算するプログラムを作成するのがタスクです。具体例を使って問題を確認しましょう。入力 −array = {5, 7, 8, 9, 10} m = 2; [0, 3], [2, 4]出力 −7 9この問題を解く方法は大きく分けて2つあります。ひとつは素直に直接計算する方法、もうひとつは累積和（prefix sum）を活用する方法です。直接計算のアプローチ：各クエリに対して、範囲の開始インデックスから終了インデックスまでループ処理を行い、該当する要素をすべて加算して

この問題では、容量がそれぞれ x と y の2つの容器と、無限に供給される水が与えられます。求められているのは、どちらか一方の容器の中でちょうど1リットルの水を測り出すことのできるプログラムを作成することです。ただし、x と y は互いに素（coprime）であるという条件が付いています。互いに素（「相対的に素」「相互に素」とも呼ばれます）とは、2つの整数の間に共通する約数が 1 のみしか存在しない関係のことです。言い換えると、両者の最大公約数（gcd：greatest common divisor）が 1 であることを意味します。この性質があるため、容器を満たしたり注ぎ足したりする操作の繰り

この記事では、n個の整数からなる配列が与えられ、そこにK個の要素を追加した後の配列の中央値を求める問題について解説します。なお、追加後の要素数「N + K」は奇数であるという条件が前提となっています。問題の概要具体的な例を使って、問題を理解しましょう。入力array = {23, 65, 76, 67} ; k = 1出力67この場合、元の配列に1つの要素を追加した結果の配列に対する中央値として「67」が出力されます。解法のアプローチこの問題を解く手順は以下の通りです。まず、与えられた配列の要素を昇順にソートします。次に、配列の末尾にk個の要素を追加することを想定します。これは、追加される要素

問題概要 データストリームから順次整数が読み込まれる状況を考えます。このとき、それまでに読み込んだ要素の中から中央値（メディアン）を、効率的な方法で求めることが課題です。 処理の流れは以下のようになります。 1つ目の要素を読み込んだ後：10 → 中央値は 10 2つ目の要素を読み込んだ後：10, 20 → 中央値は 15（平均値） 3つ目の要素を読み込んだ後：10, 20, 30 → 中央値は 20 このように、要素が追加されるたびに中央値を更新し続ける必要があります。 アルゴリズムの考え方 この問題を効率的に解くには、最大ヒープ（max heap）と最小ヒープ（min heap）を組み