C++

この記事では、C++の反復法（イテレーティブアプローチ）を使って、与えられた文字列からすべての部分列（サブシーケンス）を生成し、出力する方法を解説します。 文字列とは、複数の文字が順番に並んだ配列のことです。 部分列とは 部分列とは、元の文字列からいくつかの文字を削除することで得られる文字列であり、残った文字の並び順は元のまま変更されません。たとえば、文字列「abc」からは「a」「b」「c」「ab」「ac」「bc」「abc」といった部分列を作ることができます。 この種の問題では、「母音で始まり、子音で終わる部分列」を探すという条件が課されることもあります。たとえば次のような入出力が考えられま

この記事では、整数値の配列が与えられたときに、要素の合計が0になるすべての部分配列（連続した要素の並び）を見つけ出し、それらを出力する方法をC++で解説します。 問題の概要 まず、具体例を使って問題を理解しましょう。 入力: arr[] = {-5, 0, 2, 3, -3, 4, -1} この配列の場合、合計が0になる部分配列は以下の通りです。 {0} … インデックス1のみ {-5, 0, 2, 3} … インデックス0〜3 {3, -3} … インデックス3〜4 {-3, 4, -1} … インデックス4〜6 {-5, 0, 2, 3, -3, 4, -1} … インデックス0〜6（配

問題の概要この問題では、3つの変数 n(開始値)、s(数列の長さ)、k(差の上限)が与えられます。求めるのは、「数 n から始まり、長さ s を持ち、隣り合う要素どうしの絶対差が k 未満である」ような、考えられるすべての数列を出力することです。入力例と出力例まずは具体例を見ながら、問題をより深く理解しましょう。Input: n = 3, s = 3, k = 2 Output: 3 3 3 3 3 4 3 3 2 3 4 4 3 4 5 3 4 3 3 2 2 3 2 3 3 2 1この例では、先頭が 3 で始まる長さ 3 の数列のうち、隣接する要素の絶対差が 2 未満(つまり 0 または

この問題では、2つの整数 k と n が与えられます。そして、1からnまでの数字を使って、長さkのすべての数列をソートされた順序で出力することが求められます。具体例を見てみましょう。入力：k = 2 ; n = 3 出力： 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3つまり、この問題では上記のように、条件を満たすすべての数列を出力する必要があります。解法1：繰り返しによるアプローチ最もシンプルな解き方は、数列の各要素をインクリメントしていき、最大値nに達するまで繰り返すというものです。以下に詳しく説明します。アルゴリズム1) サイズkの配列を作成し、すべての値を1で初

この記事では、整数 N が与えられたとき、N 以下のすべての半素数を出力する方法を解説します。 半素数とは 半素数（semi-prime number）とは、2つの異なる素数の積で表される数のことです。 具体的な例を見てみましょう。 21 = 3 × 7 → 半素数である 25 = 5 × 5 → 半素数ではない（同じ素数の積のため） 問題の例 N 以下の半素数をすべて求める例を示します。 入力: N = 15 出力: 6 10 14 15 解法のアプローチ この問題を解くには、N 以下の各数について、それがちょうど2つの異なる素因数を持つかどうかを確認します。 ヒント: 最小の半素数は

問題概要 この問題では、整数 N が与えられ、その値より小さいすべての安全素数（セーフプライム）を見つけ出し、出力することが求められます。 安全素数とは？ 安全素数とは、「2 × p + 1」という形式で表すことができ、しかも p 自身も素数であるような素数のことを指します。 具体例： 5（= 2×2+1）、7（= 2×3+1）、23（= 2×11+1）などが該当します。 入出力例 Input: N = 12 Output: 5 7 11 解法アプローチ この問題を効率的に解くには、以下の手順で処理を進めます。 エラトステネスの篩を用いて、N 未満のすべての素数をあらかじめ求めます。 求めた

問題の概要 この記事では、二分木が与えられたときに、ルート（根）からリーフ（葉）までのすべての経路を出力する方法を解説します。出力の際には、アンダースコア「_」を用いて各ノードの相対的な水平位置を視覚的に表現します。 まず、具体例を見ながら内容を理解していきましょう。 入力： 出力： _ _ 3 _ 9 1 _3 9 _7 3 _ 4 _ _ 2 3 9 4 1 7 6 2 3 _ 4 6 解決のアプローチ：垂直順序の活用 この問題を解く鍵となるのは、木の要素の垂直順序（vertical order）という概念です。 上図のように、ルートの水平距離を0とし、左の子へ移動するたびに-1、右の

問題概要 この問題では、整数Nが与えられ、N以下のすべてのプロス素数（Proth Prime）を求めて出力することを目標とします。 プロス素数とは？ プロス数（Proth Number）とは、次の形式で表すことができる正の整数のことです。 N = k × 2p + 1 ここで、kは奇数の正整数、pは正の整数であり、さらに次の条件を満たす必要があります。 2p > k そして、このプロス数の中で素数であるものをプロス素数と呼びます。代表例としては、3、5、13などが挙げられます。 具体例 入力：N = 23 出力：3, 5, 13, 17 解法の考え方 この問題は、以下の手順で解くことがで

この記事では、正の整数 N が与えられたとき、N 以下に存在するすべての「素数四つ組」を見つけて出力する方法を解説します。 素数四つ組とは？ 素数四つ組とは、{p, p+2, p+6, p+8} という形で表される4つの素数の集合のことです。代表例として、「5、7、11、13」の組み合わせが挙げられます。 具体例を使って問題を確認してみましょう。 入力：N = 15 出力：5 7 11 13 解法アプローチ 1. 単純なアプローチ 最もシンプルな方法は、すべての候補 p に対して、p、p+2、p+6、p+8 がそれぞれ素数かどうかを個別に判定していくことです。この方法は実装が簡単です

問題概要この問題では、整数Nが与えられ、N以下のすべての素数を出力することが求められます。入出力例入力: 10 出力: 2 3 5 7素数とは素数とは、1とその数自身でのみ割り切れる正の整数のことです。たとえば、2、3、5、7などが該当します。単純なアプローチ最も簡単な方法は、2からNまでの各数値について、それより小さい数で順番に割っていき、どこでも割り切れなければ素数として出力するやり方です。これをNに達するまで繰り返します。ただし、この方法は1つの数を判定するのに大量の除算が必要となるため、効率面で課題があります。効率的なアプローチより効果的なのが、素数判定を「2から√Nまで」の範囲で行う

この記事では、「整数 N が与えられたとき、その数を割り切るすべての異なる素因数と、それぞれの指数（べき乗）を求めて出力する」という問題を、C++ を使って効率的に解く方法を解説します。 問題の概要 まず、具体例を見てみましょう。 入力：55 出力： 5 の指数：1 11 の指数：1 解説： 55 は 5 × 11 と素因数分解できます。どちらの素因数も 1 回しか現れないため、それぞれの指数は 1 となります。 解法のアプローチ この問題に対する基本的なアプローチは以下の通りです。 N の素因数を見つける。 各素因数が N を何回割り切れるか（＝指数）を数える。 結果を出力する。

問題概要 この記事では、与えられた数字列をもとに、昔ながらの携帯電話のテンキーでその数字を押したときに入力できるすべての単語(文字列の組み合わせ)を出力する方法を解説します。 現在広く使われているのはQWERTY配列のキーボードですが、スマートフォンが普及する以前の携帯電話には、12個のボタンからなるテンキーが搭載されていました。各ボタンには数字とアルファベットの両方が割り当てられており、たとえば「6」のキーには「MNO」が対応していて、キーを1回・2回・3回と押すことでそれぞれ「M」「N」「O」を入力できました。 当時のキーパッドの配置は以下の通りです。 12ABC3DEF 4GHI5J

問題概要 この問題では、正の整数 N が与えられ、合計がちょうど N と等しくなる連続する整数列をすべて見つけて出力します。 まず、具体例で問題を確認してみましょう。 入力：N = 15 出力： 1 2 3 4 5 7 8 上記の出力では、「1+2+3+4+5 = 15」と「7+8 = 15」の2つの連続数列が条件を満たしています。 解法1：単純な全探索（ブルートフォース） 最もシンプルなアプローチは、開始位置を 1 から N/2 まで順にずらしながら、連続する数を足し合わせていき、合計が N に一致した時点でその数列を出力する方法です。 ここで探索範囲を N/2 までに限定できるのは、2

この問題では、1つの文字列が与えられ、その文字列の各文字の間にスペースを挿入することで作成できる、すべてのパターンの文字列を出力することが求められます。具体例を使って、このトピックをより深く理解してみましょう。入力：string = XYZ 出力：XYZ, XY Z, X YZ, X Y Z解決のアプローチこの問題を解くためには、文字列内にスペースを挿入できるすべての可能な組み合わせを見つける必要があります。そのために再帰（リカージョン）を活用します。基本的な考え方は以下の通りです。各文字について、「スペースを入れない」場合と「スペースを入れる」場合の2つの選択肢があります。再帰呼び出しを通じ

問題概要 この問題では、文字の集合と正整数 k が与えられます。求められているのは、その集合に含まれる文字だけを使って生成できる、長さ k のすべての文字列を出力することです。 入出力例 Input: set = {x, y, z} , k = 2 Output: xx, xy, xz, yx, yy, yz, zx, zy, zz 解法のアプローチ この問題を解くには、生成可能なすべての文字列を網羅的に見つける必要があります。 サイズ n の集合から作れる長さ k の文字列の総数は nk 個になります。これは、各文字位置ごとに集合内の任意の文字を選べるためです。 この問題は再帰呼び出し

はじめに本記事では、m×n の2次元行列が与えられたとき、その左上（先頭要素）から右下（最終要素）まで移動可能なすべての経路を C++ で出力する方法を解説します。ただし、移動は以下の2方向に制限されるものとします。右へ1マス移動下へ1マス移動問題の例まず、具体例を使って問題を確認しましょう。入力: 1 3 5 2 8 9 出力: 1 -> 3 -> 5 -> 9 1 -> 3 -> 8 -> 9 1 -> 2 -> 8 -> 9このように、左上の「1」からスタートして右下の「9」に到達できる経路がすべて列挙されます。アルゴリズムの考え方

問題の概要この問題では、0〜9の数字からなる文字列とターゲット値が与えられます。数字の間に「+」「-」「*」の演算子を挿入して作成できる式のうち、評価結果がターゲット値と等しくなるものをすべて出力することが求められます。具体例まず、例を見ながら問題を理解しましょう。入力: string = 123、target = 6 出力: { 1+2+3, 1*2*3 }解法のアプローチこの問題は、数字の間に挿入できるすべての二項演算子の組み合わせで式を生成し、その評価結果がターゲット値と一致するかどうかを確認することで解くことができます。具体的には、再帰的な関数にすべての候補となる値を渡しながら式を評価

この記事では、サイズnの配列と正の整数rが与えられたとき、配列の要素から選んだサイズrのすべての組み合わせを出力する方法を解説します。具体例を見て、問題のイメージをつかみましょう。入力: {5, 6, 7, 8} ; r = 3 出力: {5, 6, 7}, {5, 6, 8}, {5, 7, 8}, {6, 7, 8}解法1：要素を固定して再帰的に探索するこの問題に対する基本的なアプローチは、一部の要素を固定し、残りの要素に対して再帰（またはループ）を回してすべての組み合わせを見つけるというものです。ポイントは、先頭の n-r+1 個の要素だけを固定対象にすればよいという点です。それ以降の要

「バランスの取れた文字列（balanced string）」とは、L と R という2種類の文字が同数ずつ含まれている文字列のことです。この記事では、バランスの取れた文字列 s が与えられたとき、それをできるだけ多くのバランスの取れた部分文字列に分割し、その最大個数を求める方法を C++ で解説します。 例えば、入力が RLRRLLRLRL の場合、出力は 4 になります。これは RL、RRLL、RL、RL の4つの部分文字列に分割でき、それぞれが同数の L と R を含んでいるためです。 アルゴリズムの考え方 以下の手順で問題を解きます。 カウンタ cnt と答え ans を 0 で初期

(x, y) 座標からなるデータ点のリストが与えられたとき、それらの点が一直線上に並んでいるかどうかを判定します。たとえば、点が [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7)] のように並んでいる場合、これらの点は直線を形成しています。 解決のアプローチ この問題は、隣接する2点間の差分から傾き(勾配)を求め、すべての点対で傾きが一定であるかを確認することで解けます。具体的な手順は以下のとおりです。 最初の2点の座標差 (dx, dy) を計算し、最大公約数 (GCD) で約分して基準となる方向ベクトルを作ります。 残りの各隣接点ペアについ