C++

問題の概要2つの整数 n と k が与えられたとします。ここで、a、b、c の3種類の文字のみを使用して長さ n の文字列 S を生成することを考えます。ただし、S に含まれる回文となっている部分文字列の最大の長さは、k を超えてはいけません。例えば、入力が n = 3、k = 2 の場合、出力は aab となります。文字列の長さは3であり、長さ2の回文部分文字列 aa を含んでいるためです(他の答えも存在します)。解法のアプローチこの問題は実は非常にシンプルに解くことができます。a、b、c の3文字をこの順番で繰り返す文字列(例: abcabc...)を生成すればよいのです。このような文字列

n個の要素を持つ配列Aがあるとします。この中から要素の合計が偶数になるような空でない部分集合を見つけ、その長さを求める必要があります。条件を満たす部分集合が存在しない場合は、-1を返します。 例えば、入力が A = [1, 3, 7] の場合、[1, 3] の合計は4（偶数）となるため、出力は2になります。 解法の考え方 この問題は、配列内の要素の偶奇に着目することで非常にシンプルに解くことができます。 配列内に偶数が1つでも存在すれば、その要素単独で合計が偶数になるため、答えは 1 すべての要素が奇数で、要素数が2以上であれば、任意の2つの奇数の合計は必ず偶数になるため、答えは 2 要素

問題概要 n個の要素からなる配列Aがあるとします。この配列に対して、次の操作を何度でも実行できます。 任意の正整数kを選ぶ 数列の中から任意の位置を選び、その位置にkを挿入する 数列が更新されるため、以降の操作は新しい数列に対して行う このとき、すべてのインデックスi(0以上n-1以下)について「A[i] <= i」という条件を満たすために必要な最小操作回数を求めるのが目的です。 例えば、入力が A = [1, 2, 5, 7, 4] の場合、出力は3になります。実際、次のような手順で操作を行うことで条件を満たせます。 [1,2,5,7,4] → [1,2,3,5,7,4] → [1

問題の概要2つの整数 n と k が与えられます。Amal（アマル）と Bimal（ビマル）が次のようなシンプルなルールのゲームを行います。まず Amal が紙に n 本の棒を一列に並べて描きます。その後、プレイヤーは交互に、自分の番ごとに左端または右端からちょうど k 本の棒を消していきます。先手は Amal です。ある番の直前に紙上に残っている棒が k 本未満になった場合、その時点でゲームは終了します。Amal が Bimal よりも厳密に多くの手数を指せば Amal の勝ちとなり、勝者が誰になるかを求めるのがこの問題です。例えば、入力が n = 10、k = 4 の場合、出力は「Bima

問題概要「L」「R」および 0〜9 の数字で構成される文字列 S が与えられます。ここでは、左から右へ向かって 0 から 9 までの番号が振られた 10 部屋を持つホテルを考えます。このホテルには左右 2 つの入口があります。お客様が左側の入口から到着した場合、左側の入口に最も近い空き部屋に案内されます。お客様が右側の入口から到着した場合、右側の入口に最も近い空き部屋に案内されます。残念ながら部屋割りのリストは紛失してしまいましたが、すべてのお客様について「いつ到着したか」「どちらの入口から入ったか」「いつ退去したか」という記録は残っています。ホテルは当初すべて空室でした。これらの記録をもとに

n個の要素を持つ配列Aがあるとします。一列にn個のブロックタワーが並んでおり、i番目のタワーの高さはA[i]です。1日ごとに、次の操作を1回だけ実行できます。 「2つの異なるインデックスiとj（i ≠ j）を選び、タワーiからタワーjへブロックを1つ移動する」——この操作により、A[i]は1減少し、A[j]は1増加します。 建物の「醜さ」とは、max(A) − min(A)、すなわち最も高いタワーと最も低いタワーの高さの差として定義されます。この記事では、達成可能な最小の醜さを求める方法を解説します。 問題の例 例として、入力がA = [1, 2, 3, 1, 5]の場合を考えてみましょう。

3つの整数 n、a、b が与えられたとします。私たちは n リットルの水をちょうど購入したいと考えています。近くの店で売られているのは、次の2種類の水のボトルだけです。1リットル入りボトル:価格 a ルピー2リットル入りボトル:価格 b ルピーできるだけお金をかけずに済ませたいので、ちょうど n リットルの水を購入するために必要な最小金額を求めます。入力例と出力例たとえば、入力が n = 7、a = 3、b = 2 の場合、出力は 9 になります。その理由は以下の通りです。2リットルボトルを3本購入 → 6リットル分を6ルピーで確保残り1リットルは1リットルボトルを1本購入 → 3ルピー合計金

問題概要このチュートリアルでは、試験監督に見つかることなく課題を受け渡すためのアルゴリズムをC++で実装する方法を解説します。各学生は試験監督に課題を提出しなければなりません。ここで、学生Aの課題が学生Bの手元にあるという状況を考えてみましょう。学生Bは、試験監督に気づかれることなく課題を学生Aへ返却しなければなりません。すべての学生は一列に並んで着席しています。私たちの狙いは、監督に見つからずに課題を学生Aのもとへ戻す方法を見つけることです。課題を受け渡しできる条件は以下のとおりです。ある学生（インデックスi）は、隣のインデックス（i-1）または（i+1）に座る学生にのみ課題を渡すことができ

本記事では、数字のみで構成された文字列が与えられたとき、その中に6で割り切れる部分文字列がいくつ含まれるかを求める問題を解説します。入力は数字の文字列として与えられますが、6で割り切れるかどうかの判定は、文字コード(ASCII値)ではなく、整数として扱って行う点に注意してください。問題の例入力:str = 648出力:3説明:部分文字列「6」「48」「648」が6で割り切れます。入力:str = 38342出力:4説明:部分文字列「3834」「342」「834」「42」が6で割り切れます。全探索(ブルートフォース)によるアプローチ最もシンプルな方法は、取り得るすべての部分文字列を生成し、それぞ

0〜9の数字だけで構成された文字列が与えられたとき、「8で割り切れるが、3では割り切れない」部分文字列がいくつあるかを求めるのが本記事のテーマです。一見複雑に思えますが、問題を「8の倍数の判定」と「3の倍数の除外」という2つのステップに分けて、一段階ずつコードを組み立てれば解決できます。 入出力例 入力: str = 80 出力: 2 この場合、8 と 80 の2つが条件を満たします。 入力: str = 7675636788 出力: 4 こちらは 8（2か所）、56、88 の合計4つが該当します。 解法のアプローチ まず押さえておくべき重要な性質は次の2つです。 整数が8で割り切れるかどう

はじめに このチュートリアルでは、長さNの連結リストAと整数Kが与えられたとき、サイズKごとのグループに分けて、交互にノードを反転する方法を解説します。なお、NはKで割り切れるものとします。関数の第1引数には連結リストAの先頭ポインタ、第2引数には整数Kが渡されます。 まず、入力と出力の例を見てみましょう。 入力例1 5 -> 6 -> 2 -> 8 -> 5 -> 2 -> 4 -> 8 -> 9 -> 6 -> null（K=2） 出力 6 -> 5 -> 2 -> 8 -> 2 -> 5 ->

最小全域木（MST）とは？ 全域木（spanning tree）とは、連結かつ無向のグラフにおいて、すべての頂点を接続する部分グラフのことです。ひとつのグラフには複数の全域木が存在しえますが、その中で辺の重みの合計が他のどの全域木よりも等しいか小さくなるものを最小全域木（Minimum Spanning Tree：MST）と呼びます。各辺には重みが割り当てられており、それらの総和がその全域木の重みとなります。頂点数を V とすると、最小全域木に含まれる辺の数は必ず (V − 1) 本になります。 クラスカル法で最小全域木を求める手順 すべての辺を、重みの昇順（非降順）に並べ替えます。 重み

二分木では、各子ノードが持てる子は最大2つ（左と右）です。木構造はデータを階層的に表現するシンプルな仕組みであり、その中でも二分探索木（BST：Binary Search Tree）は、次の条件を満たす特殊な二分木として定義されます。左の子ノードは、親ノードより小さい値を持つ右の子ノードは、親ノードより大きい値を持つ本記事では、「与えられた二分木の中に含まれる最大のBST（部分木）を見つけ、そのサイズを返す」関数をC++で実装する方法を解説します。二分木そのものがBSTになっている場合は、二分木全体のサイズがそのまま答えになります。問題の例例1入力： 10 /\

「Madam」や「racecar」のように、前から読んでも後ろから読んでも同じになる言葉を「回文（パリンドローム）」と呼びます。文字列のリストが与えられたとき、その中から任意の2つの文字列を選んで連結した結果が回文になるペアが存在するかどうかを判定するC++プログラムを書いてみましょう。該当するペアが存在すれば「Yes」を、存在しなければ「No」を出力します。このチュートリアルでは、入力として文字列の配列を受け取り、判定結果を文字列として出力します。以下に具体例を示します。入出力例入力list[] = {flat, tea, chair, ptalf, tea}出力Yesこの例では、「flat

はじめに 本記事では、与えられた文字列に対する「回文部分文字列クエリ」をC++で解く方法を解説します。通常の部分文字列クエリに比べ、回文の判定はコード量もロジックも格段に複雑になります。ここでは、シンプルな全探索（素朴な方法）と、効率的な動的計画法（DP）の2つのアプローチを紹介します。 問題概要 文字列 str と、Q 個のクエリ [L...R] が与えられます。各クエリは2つの整数 L と R を持ち、目的は「範囲 L から R までで形成される部分文字列が回文かどうか」を判定するプログラムを作成することです。具体例を見てみましょう。 入力文字列: abbbabaaaba（長さ11） クエ

並列配列（Parallel Array）は、「構造体配列（Structure of Arrays）」とも呼ばれるデータ構造です。 並列配列とは 定義：並列配列とは、複数の配列から構成されるデータ構造であり、各配列のi番目の要素同士が互いに密接に関連付けられ、全体で1つのエンティティ（実体）を表すものです。配列はC++言語における基本的な機能の一つであり、並列配列を作成することで、2つ以上の配列を関連付けて効率的に扱うことができます。 例： first_name = [John, Dexter, Fredd, Hank, james] last_name = [Jocab, Jonas, smi

パーティション問題とはパーティション問題とは、与えられた配列を、それぞれの要素の合計が完全に一致する2つの部分集合に分割できるかどうかを判定する問題です。この問題は「部分和問題（Subset Sum Problem）」の変形であり、部分和問題はさらに「ナップサック問題」の変形にあたります。ここではC++を使ってこの問題を解き、条件が満たされるかどうかに応じて結果を出力するプログラムを作成します。入力例arr[] = {6, 4, 8, 12, 15}出力例Is impossible to divide into two subsets of equal sumこの入力例では、配列の合計が 6+

最大5回まで使用できるバッテリーがn本あるとします。ここで、3本のバッテリーを必要とするデバイスがあり、デバイスを使用するたびにバッテリーの使用回数が1ずつ増加します。デバイスをk回使用したい場合、それらを動かすために何通りのバッテリーの組み合わせを作れるかを求める必要があります。ただし、1本のバッテリーを複数のデバイスで同時に使用することはできず、すでに5回使用されたバッテリーは組み合わせに含められません。各バッテリーの現在の使用回数は配列battとして与えられます。例えば、入力が n = 6、k = 2、batt = {2, 4, 4, 2, 1, 3} の場合、出力は 1 になります。こ

2人のプレイヤーが対戦するnラウンド制のゲームを考えてみましょう。各ラウンドのスコアは配列「scores」で与えられ、各要素は{P1のスコア, P2のスコア}という形式になっています。各ラウンドではスコアが高い方のプレイヤーがそのラウンドに勝利し、より多くのラウンドを制したプレイヤーがゲーム全体の勝者となります。両者の勝利数が同じ場合は引き分けと判定されます。この記事では、与えられたスコアをもとに、誰がゲームに勝ったのかを判定するプログラムをC++で実装します。例えば、入力が n = 4、scores = {{4, 3}, {3, 2}, {5, 6}, {2, 5}} の場合、出力は「Dra

正方形のコンテナで輸送したい n 組の箱があるとします。各組の箱の寸法はペア (a, b) として表され、それらは配列 dimensions に格納されています。箱を上下に積み重ねることはできず、各箱の幅を互いに平行にして並べる場合、箱がコンテナ内で占める面積を求める必要があります。ここでは、n 組すべてのペアについて、2つの箱を収めるために必要な最小の面積を計算します。 たとえば、入力が n = 4、dimensions = {{2, 4}, {3, 6}, {2, 5}, {4, 6}} の場合、出力は次のようになります。 64 25 36 16 解決の手順 この問題は、次の手順で解くこと