C++

このチュートリアルでは、文字列の末尾に到達するために必要な最大ジャンプ力（パワー）を求めるプログラムについて解説します。ここで扱う問題は、0と1のみで構成された文字列が与えられ、「現在位置と同じ要素に移動できる」という条件のもとで、文字列の先頭から末尾へ移動する際に必要となる最大ジャンプ力を求めるというものです。アルゴリズムの考え方ポイントとなるのは、文字列の最後の文字です。移動できるのは「現在位置と同じ要素」のみなので、実質的には最後の文字と同じ文字の位置だけを踏み台として進んでいくことになります。したがって、隣り合う同じ文字同士の間隔を数え、その最大値が答えとなります。実装例#includ

このチュートリアルでは、動的計画法（DP）の定番問題である「最大積切り分け問題（Maximum Product Cutting | DP-36）」を、C++を使って解く方法を詳しく解説します。この問題では、長さNメートルのロープが1本与えられます。私たちの課題は、このロープを複数の整数の長さに切り分けたとき、各部分の長さの積が最大になるように切ることです。問題のポイント例えば、長さ10のロープの場合、3・3・4に切り分けると積は3×3×4=36となり、これが最大値になります。単純に2等分するだけでは最適解にならないため、再帰や動的計画法を用いて全ての切り分け方を効率的に探索する必要があります。

このチュートリアルでは、「積に含まれるすべての繰り返し要素の出現回数(頻度)の合計が 2 × k 以下である」という制約のもとで、配列から達成できる最大の積を求めるプログラムについて解説します。 問題の概要 整数の配列と整数 k が与えられます。積を構成する要素の中に同じ数字が複数回現れる場合、それらの繰り返し回数の合計が 2 × k を超えてはならないという条件を満たしながら、配列から作れる最大の積を求めるのが課題です。 アルゴリズムの考え方 この問題は、ソートとハッシュマップを組み合わせることで効率的に解くことができます。手順は以下の通りです。 配列を昇順にソートします。 ハッシュマップ

このチュートリアルでは、行列内の隣接する4つの要素の積の最大値を求めるC++プログラムについて解説します。 対象となるのは正方行列です。私たちのタスクは、縦・横・斜めのいずれかの方向に隣接する4つの要素を選び、その積が最大になる組み合わせを見つけることです。 アルゴリズムの考え方 基本的なアプローチは以下の通りです。 行列のすべての要素を順番に走査します。 各要素を起点として、「横方向」「縦方向」「右下がりの斜め方向」「左下がりの斜め方向」の4パターンについて、連続する4つの要素の積を計算します。 配列の範囲外を参照しないよう、インデックスの境界条件を確認した上で計算を行います。 計算した積

このチュートリアルでは、配列の中から選んだ3つの要素（サイズ3の部分列＝トリプレット）の積が最大となる組み合わせを求めるC++プログラムについて解説します。具体的には、整数の配列が与えられ、その中から積が最大になる3要素の組み合わせを見つけるのが課題です。たとえば、配列 {10, 3, 5, 6, 20} の場合、10 × 6 × 20 = 1200 が最大の積となります。アプローチ：全組み合わせの走査（ブルートフォース法）最も基本的な方法は、3重のループで配列内のすべての3要素の組み合わせを調べることです。この方法は直感的で実装も簡単ですが、時間計算量が O(n³) と大きくなる点には注意が

はじめに 本記事では、C++を用いて「サイズ3の増加部分列の最大積」を求めるプログラムについて解説します。 具体的には、正の整数からなる配列が与えられたとき、その中から3つの要素を選んで値が増加していく部分列を作り、その積が最大になる組み合わせを見つけるという問題です。 アルゴリズムの考え方 増加する3つの要素 a < b < c の積を最大化するには、各要素を「中央の要素」として考えます。手順は以下のとおりです。 左側の探索： 注目している要素より左にあり、かつその要素より小さい値のうち、最大のものを求めます。 右側の探索： 注目している要素より右側にある値のうち、最大のものを

本記事では、増加部分列の最大積(Maximum Product of Increasing Subsequence)を求めるアルゴリズムについて、C++での実装例とあわせて詳しく解説します。 問題概要 整数型の配列が与えられます。元の配列の順序を保ったまま任意の個数の要素を選んで部分列を作り、その要素が単調増加(増加部分列)になるとき、積の最大値を求めるのが目的です。 例えば、配列 {3, 100, 4, 5, 150, 6} の場合、増加部分列 {3, 100, 150} を選ぶと積は「3 × 100 × 150 = 45000」となり、これが最大値となります。 アプローチ:動的計画法(DP

このチュートリアルでは、配列内の各要素について「左側の次に大きい要素のインデックス」と「右側の次に大きい要素のインデックス」の積を計算し、その最大値を求めるC++プログラムについて解説します。 問題の概要 整数の配列が与えられます。各要素 i に対して、以下の2つのインデックスを定義します。 L(i)：現在の要素より大きい値を持つ、左側で最も近い要素のインデックス R(i)：現在の要素より大きい値を持つ、右側で最も近い要素のインデックス そして、すべての要素の中で L(i) × R(i) が最大となる値を求めるのがこの問題の目的です。左右どちらにも大きい要素が存在しない場合は、そのイン

このチュートリアルでは、n個の配列から「昇順」という条件を満たすように要素を1つずつ選び、その合計を最大化するプログラムについて解説します。 ここでは、サイズMの配列がN個与えられます。各配列から1つずつ要素を選び、「前の配列から選んだ要素よりも、次の配列から選ぶ要素の方が大きい」という条件を満たしながら、合計の最大値を求めることが課題です。 アルゴリズムの考え方 この問題は、貪欲法（グリーディ法）を用いることで効率的に解くことができます。手順は以下の通りです。 まず、すべての配列をそれぞれ昇順にソートします。 最後の配列の最大要素（末尾の要素）を出発点とし、これを合計の初期値とします。 後

はじめに本記事では、動的計画法(Dynamic Programming)を用いて、「隣接する2つのノードを同時に選ばない」という制約のもとで、二分木のノード値の合計の最大値を求めるアルゴリズムについて解説します。具体的には、二分木が与えられたとき、親子関係にある(直接つながっている)ノード同士を同時に選ばないという条件を満たすノードの部分集合の中から、ノード値の合計が最大になるものを見つけることが課題です。アルゴリズムの考え方木構造上の動的計画法では、各ノードに対して次の2つの状態を定義するのが定石です。dp1[node]:そのノード自身を「選ぶ」場合の、その部分木における最大合計dp2[no

このチュートリアルでは、二分木において「互いに隣接しないノード」だけを選んだときのノード値の最大合計を求めるプログラムを、C++を使って解説します。問題の設定は次のとおりです。二分木が与えられたとき、親子関係にあるノード同士(直接つながっているノード)を同時に選ばないという条件を満たすノードの部分集合の中から、値の合計が最大になるものを見つけることが課題です。アプローチ:動的計画法とメモ化この問題は、動的計画法(DP)にメモ化を組み合わせることで効率的に解けます。各ノードに対して、次の2つの選択肢を比較します。そのノードを選ぶ場合: ノード自身の値に加えて、孫ノード(子のさらに下のノード)以降

はじめにこのチュートリアルでは、C++を使って「差がK未満となるペアの最大合計」を求めるプログラムについて解説します。具体的には、整数の配列と値Kが与えられたとき、差がK未満になる要素同士をペアに組み合わせます。ただし、同じ要素を複数のペアに使うことはできません（互いに素な集合である必要があります）。この条件のもとで、選ばれたペアの要素の合計の最大値を求めるのが目的です。解き方のポイント：動的計画法この問題を効率的に解くには、動的計画法（DP）を活用します。まず配列を昇順にソートし、隣接する2つの要素の差がK未満であれば「それらをペアにするかどうか」をDPテーブルで判断していきます。アルゴリズ

はじめに このチュートリアルでは、負の数を含む配列において、要素をペアにして積を計算した際の合計の最大値を求めるプログラムをC++で解説します。 整数の配列が与えられたとき、任意の2つの要素をペアとして掛け合わせ、すべてのペアの積の総和が最大になるような組み合わせを見つけるのが課題です。 アルゴリズムのポイント 最大の合計を得るためには、次のような貪欲法（グリーディ法）の戦略が有効です。 負の数同士をペアにする：負 × 負 ＝ 正 になるため、絶対値の大きい負の数同士（昇順ソート時の先頭側）から2つずつペアにすると、大きな正の値が得られます。 正の数同士をペアにする：大きい値同士を掛けるほど

はじめに 本記事では、2つの配列の積の最大合計（Maximum Sum of Products）をC++で求めるプログラムについて解説します。 この問題では、同じサイズを持つ2つの配列が与えられます。私たちのタスクは、一方の配列の要素ともう一方の配列の要素を1対1で掛け合わせ、その積の総和が最大になるような組み合わせを見つけることです。 解き方のアプローチ：貪欲法 この問題は貪欲法（グリーディ法）を使うことで効率的に解けます。考え方はシンプルです。 まず、両方の配列をそれぞれ昇順にソートします。 次に、小さい値同士・大きい値同士を対応付けて掛け合わせます。 負の数が含まれる場合でも、「マイ

本チュートリアルでは、配列内の「最小値」と「2番目に小さい値」の合計の最大値を求めるC++プログラムについて解説します。問題の概要整数の配列が与えられたとき、考えられるすべての部分配列(連続する要素の組み合わせ)の中から、それぞれの部分配列における最小値と2番目に小さい値の合計を計算し、その中で最も大きくなる値を見つけることが課題です。解法のポイント一見するとすべての部分配列を調べる必要があるように思えますが、実は隣接する2要素のペアだけを確認すれば十分です。部分配列が長くなるほど、その中の最小値や2番目に小さい値は小さくなる(または変わらない)傾向があるため、隣接ペアの合計を超えることはない

このチュートリアルでは、C++を使って、N×Nの行列（マトリックス）の最上行から最下行までの「最大合計パス」を求める方法を解説します。 問題の概要 N×Nサイズの整数行列が与えられます。最上行のいずれかのセルから出発し、1行ずつ下へ進みながら最下行に到達するまでの経路のうち、通過したセルの値の合計が最大になるものを見つけるのが目的です。移動先として選べるのは、次の行の斜め下（左下または右下）のセルのみです。 アプローチ：動的計画法（DP） すべての経路を総当たりで調べると計算量が爆発的に増えてしまいますが、動的計画法を使えばO(N²)の計算量で効率的に解くことができます。手順は以下の通りです。

このチュートリアルでは、配列内のどの2つの要素も互いに距離がK未満にならないように要素を選んだときの、部分列の最大合計値を求めるプログラムについて解説します。 N個の整数からなる配列と値Kが与えられます。私たちのタスクは、互いにK以上離れた位置にある要素だけを選んで構成した部分列のうち、合計値が最大になるものを見つけることです。 アルゴリズムの考え方（動的計画法） この問題は、動的計画法（DP）を用いることで効率的に解くことができます。各インデックスiについて、「その位置までの要素を考慮したときの最大和」をdp[i]として順に記録していきます。 初期条件：dp[0] = arr[0] i ≤

はじめに本チュートリアルでは、2次元行列における最大合計長方形(Max Sum Rectangle)を求めるプログラムについて解説します。具体的には、正数と負数が混在する2次元行列が与えられたとき、要素の合計が最大となる部分矩形(サブマトリクス)を効率よく見つけることが課題です。これは動的計画法(DP)の代表的な応用問題の一つであり、「DP-27」としても知られる定番テーマです。アルゴリズムの考え方この問題は、1次元配列の最大部分配列和を線形時間で求める有名なKadaneのアルゴリズムを2次元へ拡張することで解くことができます。基本的な手順は以下の通りです。左端の列 left を固定し、右端の

はじめにこの記事では、「先頭と末尾の要素の値が等しい」という条件を満たす部分配列（サブ配列）の中から、合計が最大となるものを求めるプログラムについて解説します。具体的には、整数からなる配列が与えられたとき、両端の要素が同じ値である部分配列を探し、その中で合計が最大になるものを見つけるのが目的です。アルゴリズムの考え方この問題は、次の手順で効率的に解くことができます。あらかじめ累積和（プレフィックスサム）を計算しておく。ハッシュマップを使い、各値が最初に出現する位置と最後に出現する位置を記録する。各要素について「最初の出現位置」から「最後の出現位置」までの区間の合計を累積和で求め、その最大値を答

はじめに このチュートリアルでは、「少なくともK個離れた要素からなる最大和部分列」を求めるプログラムについて解説します。動的計画法(DP)を活用することで、効率よく最適解を導き出すことができます。 問題の概要 整数を含む配列と値Kが与えられます。求めるのは、選ばれたどの2つの要素の間にも少なくともK個の要素が存在する(インデックスの差がK+1以上である)という制約を満たしながら、合計値が最大となる部分列です。 アルゴリズムの考え方 この問題は動的計画法で解くことができます。MS[i] を「インデックスi以降で選択可能な要素の合計の最大値」と定義し、配列を後ろから前に向かって走査していきます