C++

本記事では、二分木の高さHが与えられたとき、その高さを持つ平衡二分木（バランスの取れた二分木）が何通り存在するかをC++で求める方法を解説します。 二分木とは 二分木（バイナリツリー）とは、各ノードが最大2つの子ノード（左の子と右の子）を持つ木構造のデータ構造です。 高さ平衡二分木とは 高さ平衡二分木（height-balanced binary tree）とは、すべてのノードにおいて、左部分木と右部分木の深さの差が0または1しかない二分木として定義されます。つまり、どのノードを見ても、左部分木と右部分木の高さの差は最大で1である必要があります。 次の図は、高さh=3の場合に考えられる高さ平衡

サイズ N の整数型配列が与えられます。この記事の目的は、その配列の中から「最大積」と「最小積」を生み出す部分集合を見つけることです。ここでは、これまでに見つかった最大積を保持する maxProd、最小積を保持する minProd という2つの変数を使って問題を解いていきます。 配列を先頭から走査しながら、各要素を maxProd と minProd の両方に掛けていきます。同時に、直前の最大積(prevMax)、直前の最小積(prevMin)、現在の最大積(curMax)、現在の最小積(curMin)、そして現在の要素そのものも常にチェックすることがポイントです。 入力例 Arr[]= {

問題概要2つの正の整数 num1 と num2 が与えられます。この問題の目標は、両方の数値に対して桁(数字)の置き換えを行った後に実現できる最小の合計値と最大の合計値を求めることです。たとえば、num1 が 434、num2 が 324 であり、「3 を 4 に置き換える」「4 を 3 に置き換える」ことが許されている場合を考えてみましょう。最小の合計：333 + 323 = 656(すべての 4 を 3 に置き換える)最大の合計：444 + 424 = 864(すべての 3 を 4 に置き換える)入力例と出力例例1入力：num1=3224 num2=4321出力：Maximum sum i

正と負の整数で構成される配列と数値Kが与えられます。求めるのは、配列の要素に対してちょうどK回の変更を行った後の合計の最大値です。ここでいう1回の変更操作とは、単一の要素に-1を掛けて符号を反転することを指します。アルゴリズムの考え方基本的なアプローチは、すべての負の数を正の数に変換することです。負の数がN個ある場合、まず配列をソートしてから以下の方針で処理します。N < K の場合：N回の操作ですべての要素が正となり、残りはK−N回の操作になります。K−N が偶数の場合：残りのK−N回の符号反転は互いに打ち消し合うため、何もする必要がありません。K−N が奇数の場合：配列内の最小値（最

正の整数からなる配列が与えられたとき、その中に存在する「連続した整数」(値が1ずつ増えていく並び)の最大個数を求めることを考えます。 基本的な考え方は次のとおりです。まず配列を昇順にソートし、隣接する要素同士を比較します。arr[j]==arr[i]+1(j=i+1)が成り立てば連続していると判断できるため、カウントを1増やしてインデックスを進めます(i++、j++)。差が1でなければcountを1にリセットします。そして、それまでに見つかった最大のカウントをmaxcに記録していきます。 入力例1 Arr[]= { 100,21,24,73,22,23 } 出力例1 Maximum cons

整数の配列が与えられたとき、以下の操作を繰り返し行った後に、配列内で等しくできる要素数の最大値を求める問題を考えます。i != j となる2つの要素 a[i] と a[j] を選ぶa[i] を1増やし、a[j] を1減らす(a[i]++、a[j]--)この操作では、1つの要素を増やして別の要素を減らすため、配列の合計値は常に一定であるという重要な性質があります。そこで、配列の合計値を要素数で割ることを考えます。配列のサイズを N とすると、次のように判定できます。合計値が N で割り切れる場合:すべての要素を平均値に揃えられるため、等しくできる要素数は N割り切れない場合:少なくとも1つの要素

整数の配列が与えられたとき、配列内の2つの要素からなるペアを足し合わせた結果が同じ合計となるペアのうち、最も多く存在するケースのペア数を求めるのがこの問題の目的です。同じ合計を生成するペアが最大でいくつ現れるかを計算します。 入力例 Arr[]= { 1,2,3,4,2 } 出力例 同じ合計を持つペアの最大数 : 3 説明 − 各ペアの合計は以下のようになります − {1,2}, {1,2} 合計:3 {1,3},{2,2} 合計:4 {1,4},{2,3},{3,2} 合計:5 {2,4} 合計:6 {3,4} 合計:7 同じ合計を持つペアの最大数は3です(合計 = 5 の場合) 入力例

整数の配列が与えられます。この配列は、昇順にソートされた配列をある位置で回転させたもの（ソート済み回転配列）です。ここでの目標は、配列に含まれる要素のうち、指定された値 K 以下であるものの個数を求めることです。 基本的なアプローチはとてもシンプルで、配列全体を一度走査しながら、K 以下の要素を順に数え上げるというものです。回転によって大小関係が崩れているため、通常の二分探索をそのまま適用することはできません。そこで、まずはこの線形走査による確実な方法を確認していきましょう。 入力例と出力例 例 1 Arr[] = { 1,2,3,4,9,8,10 } , K = 4 4 以下の要素の数 :

問題の概要 整数からなる配列が与えられます。この記事の目的は、次の条件を満たす配列中の要素の個数を求めることです。 条件：各要素について、「その要素自身を除いた配列内の、その値以上の数値の個数」が、ちょうどその値自身と一致すること。 言い換えれば、ある要素が X であるとき、配列には X 以上の数値がちょうど X 個存在しなければなりません（ただし要素そのものは数えません）。 入力例 1 Arr[]= { 0,1,2,3,4,9,8 } 出力 条件を満たす要素の個数 : 1 解説：各要素ごとに「その値以上の要素の個数」と比較すると、次のようになります。 Arr[0]: 値 0 以上の要素

問題概要 バイナリ列(0と1からなる数列)に対して、その半分の長さにあたるビット数 n が入力として与えられます。求めたいのは、前半 n ビットの合計(1の個数)と後半 n ビットの合計が一致する、長さ 2n のバイナリ列の総数です。 バイナリ列なので、各位置に入れられる値は 0 か 1 のみです。まず、n ビットの中に含まれる 1 の個数ごとの組み合わせ数を整理してみましょう。 1 が 0 個:nC0 = 1 通り 1 が 1 個:nC1 通り 1 が 2 個:nC2 通り …… 1 が n 個:nCn 通り 次に、長さ 2n の列全体を考えます。前半と後半で合計が一致するためには

1からnまでの範囲の値を持つ要素からなる配列が与えられます。一部の要素は複数回出現し、逆に一度も出現しない要素もあります。ここでの課題は、O(n)の計算時間とO(1)の追加メモリという制約のもとで、すべての要素の出現頻度を求めることです。入力例1Arr[]= { 1,2,2,3,4,4,4,5 }出力例11→ 1, 2→ 2, 3→ 1, 4→ 3, 5→ 1解説：最大値は5であり、出力は各要素が配列内に出現した回数を示しています。入力例2Arr[]= { 1,4,4,5,5,5,5 }出力例21→ 1, 2→ 0, 3&r

最初のN個の自然数の順列からなる配列が与えられます。この記事の目的は、次の条件を満たす要素のインデックスペアを見つけることです。配列を Arr[]、i と j をインデックスとするとき、Arr[i] + Arr[j] = max(Arr[x])（ただし i ≦ x ≦ j）となる要素ペアを数えます。つまり、Arr[i] と A[j] の和が、この2つの区間の間に存在する最大要素と一致しているかどうかを判定します。入力例1Arr[]= { 2,4,1,3,6,5 }出力例1条件を満たすインデックスペアの数：1解説各ペアの和は以下のようになります。2+4=6 → 6は最大値ですが、2と4の間には存

1からnまでの数字が重複なく格納された配列が与えられます。この記事の目的は、与えられた配列を昇順にソートするために必要な「先頭へ移動(move-to-front)」操作の最小回数を求めることです。「先頭へ移動」とは、配列内の任意の要素を取り出して、先頭(インデックス0)に配置する操作を指します。この問題は、配列を末尾から先頭に向かって走査することで効率的に解けます。要素がすでに正しい位置にあれば移動は不要ですが、そうでなければ移動が必要です。1からnまでの要素で構成されるソート済み配列では、各要素arr[i]の正しい値はi+1である必要があります。つまり、arr[0]=1、arr[1]=2、…

同じ配線に直列に接続された電球のON/OFF状態を、0と1からなる配列で表現します。0は消灯(OFF)、1は点灯(ON)を意味します。このようなN個の電球の並びにおいて、ある電球のスイッチを押すと、その右側にあるすべての電球(i+1番目からn番目まで)の状態が反転し、ONだった電球はOFFに、OFFだった電球はONに変わります。与えられた電球の状態をもとに、すべての電球を点灯させるために押す必要があるスイッチの最小回数を求めるのがこの問題の目的です(同じスイッチは何度押しても構いません)。これは、配列内の右側のインデックスの値を反転させて、すべての値を1に設定する操作と同等です。入力例Bulb

問題概要 数値を含む配列 target[] が与えられます。すべての要素が0である配列 [0,0,0,…] を、次の2つの操作のみを使って target[] に変換するとき、必要な最小ステップ数を求めるのが課題です。 インクリメント操作: 要素を1つずつ選んで1増やします。各インクリメントは個別にステップとしてカウントされます(n個の要素にn回のインクリメントを行う場合、ステップ数はn)。 倍加操作(ダブリング): 配列全体を一括して2倍にします。すべての要素が同時に2倍になるため、この操作は1ステップとしてカウントされます。 たとえば [0,0,0] は、全要素へのインクリメント操作によ

問題概要 同じ長さの文字列からなる配列が与えられたとき、縦方向(列ごと)に見て昇順にソートされていない列がいくつあるかを数えるのが、この問題の目的です。 具体的な手順は次のとおりです。まず、すべての文字列の1文字目同士を上から下へ比較し、続いて2文字目同士、3文字目同士というように、同じ位置にある文字を順番に調べていきます。ある列の中で「前の文字より後ろの文字が小さい」という箇所がひとつでもあれば、その列は昇順ではないと判定し、カウントを1つ増やします。 入力例と出力例 例1:すべての列が昇順の場合 Arr[] = { "abc", "bcd", &qu

本記事では、循環配列（サーキュラー配列）に格納された複数の数値を連結し、可能な限り大きな数を作り出す問題をC++で解きます。循環配列とは、先頭の要素が末尾の要素の直後に続くものとして扱われる配列のことで、キュー（待ち行列）の実装などによく利用されます。問題の概要配列内の各要素は、桁数が同じでも異なっていても構いません。目標は、必要に応じて要素を回転（ローテート）させながら数値を連結し、最大の数を生成することです。この問題は、すべての要素の左端の桁（最上位の桁）に注目することで解けます。その中で最も大きい左端の桁を持つ数が、連結後の数の先頭に配置されるべきです。その要素が先頭（インデックス0）に

はじめに 本記事では、0と1だけで構成された正方行列が与えられたとき、「下から右方向へ光を伝送できる鏡」の最大数を求めるアルゴリズムをC++で解説します。 問題の定義 行列の各要素は次の意味を持ちます。 0 … 空きセル(何もない場所) 1 … 障害物 空きセルの中から鏡を設置できる場所を見つけ、それらの鏡が下から右へ光を伝送できるようにすることを目標とします。 具体的には、鏡がセル [i, j] に配置できるのは、同じ行 i の右側にあるすべてのセルと、同じ列 j の下側にあるすべてのセルに障害物が存在しない場合です。 言い換えると、A[i][j] に鏡を置くためには、A[i+1〜n

整数 a、b、c、n が与えられたとき、ax + by + cz = n を満たす x + y + z の合計を最大化することが目標です。 式の導出 与えられた式から、z は次のように表すことができます。 cz = n − (ax + by) z = (n − (ax + by)) / c x と y を固定すれば、この式から z を一意に求められます。すべての x・y の組み合わせについて z を計算し、その合計 x + y + z を求めます。そして、条件を満たす組み合わせの中で最も大きい合計を答えとして記録していきます。 入力例と出力例 例1 n = 6, a = 3, b = 4, c

問題概要整数の配列が与えられたとき、次の式の値を最大化することが目的です。arr[j]-arr[i] + arr[l]-arr-k(ただし、i<j<k<l は要素のインデックス)この問題は、すべての要素の組み合わせを走査して式の値を計算し、これまでに見つかった最大値よりも大きい場合はその値を記録していき、最後に最大値を返すことで解くことができます。入力例arr[]= { 1,2,3,4 }出力例上記の式の最大値 : 2説明: i<j<k<l を満たすのは i=0, j=1, k=2, l=3 のときです。arr[j]-arr[i]+arr[l]-arr[k]