C++

問題概要 0、1、およびその他の英字を含む文字列 str が与えられます。この文字列には「1(0+)1」という形式のパターンが含まれていることがあります。ここで「0+」は、1個以上の連続する0を意味します。この記事の目的は、文字列 str 内にこのパターンが何回出現するかを数えることです。 入出力例 例1 入力 − str = abb010bb10111011 出力 − 「1(0+)1」パターンの出現回数： 2 説明 − パターンに該当するのは 101 と 101 の2箇所です。 例2 入力 − str = 01001011001001100 出力 − 「1(0+)1」パターンの出現

問題概要 整数 num が入力として与えられます。求めたいのは、((num % i) % j) % num の値が最大になるときのペア (i, j) の個数です。ここで i と j は、どちらも範囲 [1, num] に含まれる整数とします。 入出力例 入力： num = 4 出力： 3 説明： 条件を満たすペアは (3, 2)、(3, 3)、(3, 4) の 3 つです。 入力： num = 6 出力： 4 説明： 条件を満たすペアは (4, 3)、(4, 4)、(4, 5)、(4, 6) の 4 つです。 解法①：ナイーブなアプローチ（全探索） 剰余演算の性質上、ある数 n を「n

本記事では、整数 num が入力として与えられたとき、「隣接する文字同士のASCII値の差がちょうど1である」という条件を満たす長さ num の文字列の総数を、C++ の動的計画法（DP）を用いて効率的に求める方法を解説します。 例えば num が 2 の場合、条件を満たす文字列は「ab」「ba」「bc」「cb」……「yz」「zy」となります。 具体例 入力： num = 3 出力： 隣接する文字の差が1である文字列の個数 ― 98 説明： 条件を満たす文字列の例としては、「abc」「aba」「cde」……「xyx」「zyz」「xyz」などが挙げられます。 入力： num = 2 出力： 隣接

問題概要一辺の長さが与えられた正三角形を考えます。この記事の目的は、水平な2辺が底辺と平行になるように三角形の内部へ配置できる「異なる長方形」の総数を数えることです。ただし、長方形の4つの頂点はすべて、図に示された点(格子点)に一致していなければなりません。入出力例入力 − sides=3出力 − 正三角形に内接する異なる長方形の数:1説明 − 上の図は条件を満たす長方形を示しています。入力 − sides=10出力 − 正三角形に内接する異なる長方形の数:200アルゴリズムの考え方図から分かるように、長方形の水平な辺は、一段おきのレベルにある点同士を結ぶ形になります。そのため、点の数はレベル

この記事では、n個の整数からなる配列arr[]が与えられたとき、その中から3つの要素（サイズ3の部分列＝トリプレット）を選び、積が最大となる組み合わせを見つけて、その最大積を返す方法を解説します。問題例入力arr[] = {9, 5, 2, 11, 7, 4}出力693説明配列全体の中で最も大きな積となるトリプレットは「9 × 11 × 7」であり、その積は693となります。解法アプローチこの問題には複数の解き方が存在します。ここでは代表的な3つの手法を、アルゴリズムと実装例とともに紹介します。方法1：全探索（ブルートフォース）最もシンプルな方法です。配列を三重ループで走査し、考えられるすべて

問題の概要この問題では、n個の正の整数からなる配列 arr[] が与えられます。求めるのは、サイズ3の増加部分列における最大の積です。具体的には、以下の条件を満たす3つの要素の組み合わせのうち、積が最大になるものを見つける必要があります。arr[i] * arr[j] * arr[k] が最大arr[i] < arr[j] < arr[k] かつ i < j < kつまり、値が増加しており、かつインデックスの順序も増加している3つの要素を選ぶ必要があります。入出力例入力:arr = {5, 9, 2, 11, 4, 7}出力:495説明:条件を満たすサイズ3の部分列は以

本記事では、サイズnの整数型配列arr[]が与えられたとき、「増加部分列（Increasing Subsequence）」の中で要素の積が最大となる値を求める問題を、C++を使ってわかりやすく解説します。 問題の概要 配列内の要素から任意の長さの増加部分列を選び、その積の最大値を求めることが目的です。増加部分列とは、元の配列の順序を保ちながら、各要素が直前の要素よりも大きくなるような部分列のことを指します。 入出力例 入力 arr[] = {5, 4, 6, 8, 7, 9} 出力 2160 解説 考えられる増加部分列： {5, 6, 8, 9} → 積 = 2160 {5, 6, 7,

この記事では、配列 arr[] が与えられたときに、「左側・右側にある次に大きい要素のインデックスの積」の最大値を計算するC++プログラムを作成する方法を解説します。問題の概要与えられた配列に対して、left[i] * right[i] の最大値を求める必要があります。ここで、left配列とright配列はそれぞれ次のように定義されます。left[i] = j ： arr[i] < arr[j] かつ i > j を満たすjright[i] = j ： arr[i] < arr[j] かつ i < j を満たすj※ 配列は1始まりのインデックスです。つまり、各要素につい

この問題では、n個の整数からなる配列 arr[] が与えられ、その中から部分集合を選んで積の最大値(最大積部分集合)を求めるプログラムを作成します。問題の概要配列の要素から任意の部分集合を選び、その積として考えられる最大値を計算します。部分集合 − 配列 sub[] のすべての要素が配列 arr[] に含まれているとき、sub[] は arr[] の部分集合とみなされます。具体例で問題を理解する入力arr[] = {4, 5, 2, -1, 3}出力40説明部分集合 sub[] = {4, 5, 2}積 = 4 × 5 × 2 = 40解法アプローチ1. 単純な方法(全列挙)最もシンプルなのは

この記事では、n個の整数からなる配列 arr[] が与えられたとき、指定された条件を満たす部分配列（サブ配列）の最大サイズを求めるプログラムを C++ で作成する方法を解説します。問題の概要目的は、以下のいずれかの条件を満たす最長の部分配列の長さを求めることです。k が奇数のとき arr[k] > arr[k+1]、k が偶数のとき arr[k] < arr[k+1] が成立すること（部分配列のすべての要素に対して）k が奇数のとき arr[k] < arr[k+1]、k が偶数のとき arr[k] > arr[k+1] が成立すること（部分配列のすべての要素に対して）

問題概要この問題では、0と1のみで構成された n × m の2次元行列 bin[][] が与えられます。私たちの課題は、すべての要素が1で構成される長方形の部分行列のうち、面積が最大になるものを見つけ、その最大面積を返すプログラムを作成することです。具体例を使って問題を確認してみましょう。入力bin[][] = { {1, 0, 1, 1, 1} {0, 1, 1, 1, 1} {0, 0, 1, 1, 1} {1, 1, 1, 1, 1} }出力12説明以下の部分行列（4行 × 3列）が最大の面積12を持ちます。1, 1, 1 1, 1, 1 1, 1, 1

この問題では、クラス内の各学生の試験点数を格納したサイズ n の配列 stu[] が与えられます。各学生の満点は100点であり、合格には50点以上が必要です。全員に一律でボーナス点を加算し、かつ誰の点数も100点を超えないという条件のもとで、合格できる学生の最大人数を求めるプログラムを作成することが課題です。 問題の概要 合格者を増やすために学生へボーナス点を与えますが、このボーナスはクラス全体に対して同じ値を加算しなければなりません。誰かの合計点が100点を超えてしまわない範囲でボーナス点を設定し、それによって合格できる学生の数を最大化します。最後に、合格できる学生の最大人数を返します。 入

この記事では、0と1だけで構成された n×n の2次元行列が与えられたときに、「1の個数が0の個数よりちょうど1つ多い」部分行列のうち、面積（要素数）が最大になるものを求めるC++プログラムを解説します。 問題の例 入力 bin[N][N] = { {0, 1, 0, 0}, {1, 1, 0, 0}, {1, 0, 1, 1}, {0, 1, 0, 1} } 出力 9 説明 部分行列： bin[1][0], bin[1][1], bin[1][2] bin[2][0], bin[2][1], bin[2][2] bin[3][0], bin[3][1], bi

問題概要 この問題では、二分木 BT が与えられ、「その部分木自身も二分探索木（BST）である」という条件を満たす部分木の中から、ノード値の合計が最大となるものを見つけるプログラムを作成します。 二分木（Binary Tree）とは 二分木とは、各ノードが最大2つの子ノードを持つことができる特殊な木構造です。 二分探索木（BST）とは 二分探索木とは、すべてのノードが以下の性質を満たす木のことです。 左部分木のキー値は、親（ルート）ノードのキー値より小さい。 右部分木のキー値は、親（ルート）ノードのキー値以上である。 入出力例 入力： 出力： 32 説明：この木には BST として成立し

この記事では、n個の正の整数からなる配列 arr[] と整数 k が与えられたときに、「そのサイズのすべての部分配列の合計が k 未満となる最大の部分配列サイズ」を求めるC++プログラムを紹介します。 問題の概要 配列の要素から構成できるあるサイズの部分配列をすべて考えたとき、どの部分配列を取っても要素の合計が k 以下になるような、最大のサイズを見つけるのが目標です。 具体例で理解しよう 入力 arr[n] = {4, 1, 3, 2}, k = 9 出力 3 説明 サイズ3の部分配列とその合計は次のようになります。 {4, 1, 3} = 8 {1, 3, 2} = 6 サイズ3のすべての

この問題では、サイズ n の配列 arr1[] と、サイズ m の配列 arr2[] の2つが与えられます。私たちのタスクは、arr2[] に含まれる要素を除外した状態で、arr1[] の最大部分配列の和（Maximum Subarray Sum）を求めるプログラムを作成することです。問題の概要配列 arr1[] の要素のうち、arr2[] に存在しない要素のみを使って、連続する部分配列の和が最大になるものを見つける必要があります。入力例arr1[] = {4, 5, 7, 2, 9}, arr2[] = {1, 9, 2, 7}出力例9解説arr1[] から arr2[] の要素 {7, 2

この記事では、サイズnの配列arr[]と整数kが与えられたとき、配列をk回繰り返し連結して作成される新しい配列から、最大部分配列の合計を求めるプログラムをC++で実装する方法を解説します。問題の概要元の配列arr[]をk回繰り返して連結することで新しい配列を作成し、その中で合計値が最大となる部分配列（連続する要素の集まり）を見つけ、その合計を求めるのが目的です。入出力例具体的な例を使って問題を確認してみましょう。入力arr[] = {-9, -5, 14, 6}、k = 2出力26説明繰り返し連結後の新しい配列 : {-9, -5, 14, 6, -9, -5, 14, 6} 最大合計を持つ部

問題概要この問題では、n個の正の整数からなる配列 arr[] が与えられます。求めるのは、「3つの連続した要素を選ばない」という制約のもとで、選んだ要素の和を最大化することです。ここでいう「連続する要素」とは、配列内でインデックスが順番どおりに並んでいる要素のことを指します。arr[0], arr[1], arr[2], …入出力例入力arr[] = {5, 9, 12, 15}出力32説明和 = 5 + 12 + 15 = 32この例では、9 を除外することで「3連続」を避け、残りの要素をすべて選んでいます。もし {9, 12, 15} のように3つ連続で選ぶと制約違反となるため、{5, 1

この問題では、n個の整数からなる配列 arr[] が与えられます。目的は、配列の最初の要素から始まる最大和の交互部分列を見つけるプログラムを作成することです。 交互部分列とは、要素が「減少 → 増加 → 減少」のように増減を交互に繰り返す部分列のことです。なお、この問題では逆順の交互部分列（最初に増加するパターン）は、最大和を求めるうえで有効な候補として扱いません。 それでは、具体例を使って問題を理解しましょう。 入力例 arr[] = {5, 1, 6, 2, 4, 8, 9} 出力 27 説明 開始要素：5 → 減少：1 → 増加：6 → 減少：2 → 増加：4 → 以降選択不可 ここでは

この問題では、2つの配列 arr1[] と arr2[]、および2つの整数 N と M が与えられます。N は arr1 から選択できる要素の最大数、M は arr2 から選択できる要素の最大数を表します。各インデックス i において、arr1[i] と arr2[i] のどちらか一方の要素を選び、合計が最大になるようにします。ただし、arr1 からは最大 N 個、arr2 からは最大 M 個までしか選択できないという制約があります。本記事では、C++ を使って2つの配列から順番に要素を選択し、最大合計を求めるプログラムの作成方法を解説します。入力例と出力例入力arr1[] = {5, 1,