C++

問題概要2つの整数配列 A と B が与えられ、それぞれ別々の水平な直線上に、与えられた順序どおりに並べて書かれているとします。ここで、次の条件を満たす「接続線」を引くことを考えます。A[i] == B[j] を満たす2つの数 A[i] と B[j] を結ぶこと引いた線が、他のどの接続線(水平線は除く)とも一切交差しないこと重要なのは、接続線どうしは端点同士でも接触してはいけないという点です。つまり、1つの数値が属せる接続線は高々1本だけです。この条件下で、引くことのできる接続線の最大本数を求めます。たとえば、入力が [1,4,2] と [1,2,4] の場合、答えは 2 になります。1421

問題概要値 N が与えられ、頂点が A[0], A[1], ..., A[N-1] と時計回りに並んだ凸 N 角形を考えます。この多角形を N-2 個の三角形に分割する「三角分割」を行います。各三角形の値はその頂点ラベルの積として定義され、三角分割全体のスコアは N-2 個の三角形の値の合計となります。ここでの目標は、さまざまな三角分割の方法の中から達成可能な最小の合計スコアを見つけることです。たとえば、入力が [1,2,3] の場合、出力は 6 になります。これは多角形がすでに三角形そのものであり、唯一の三角形のスコアが 1 × 2 × 3 = 6 となるためです。解法アプローチ(区間DP)

無限に広がる平面上に、初期位置 (0, 0) で北を向いて立つロボットがあります。このロボットは次の3種類の命令を受け取ることができます。G … 現在向いている方向へ1単位まっすぐ進むL … 左に90度回転するR … 右に90度回転するロボットは与えられた命令列を順に実行した後、同じ命令列を永遠に繰り返します。ここで、平面上に「ロボットが二度と外に出ない円」が存在するかどうかを判定します。例えば入力が "GGLLGG" の場合、答えは true になります。ロボットは (0, 0) から (0, 2) へ移動した後、元の位置と向きに戻る閉じた経路に入り、以後その領域を永遠に

問題概要 小文字だけで構成された単語のリストが与えられます。ある単語 word1 が別の単語 word2 の「先行詞(predecessor)」であるとは、word1 の任意の位置にちょうど1文字を追加するだけで word2 と一致させられる場合を指します。たとえば、「abc」は「abac」の先行詞です。 「単語チェーン」とは、[word_1, word_2, ..., word_k](k ≥ 1)という単語の列で、word_1 が word_2 の先行詞、word_2 が word_3 の先行詞、というように隣接する単語同士がすべて先行詞の関係になっているものを指します。ここでの目的は、与え

問題概要 正の整数の重みを持つ石が複数与えられます。各ターンごとに、任意の2つの石を選んで衝突させます。2つの石の重みをそれぞれ x と y（x ≤ y）としたとき、衝突の結果は以下のようになります。 x = y の場合：両方の石は完全に砕けて消滅します。 x ≠ y の場合：重み x の石は完全に破壊され、重み y の石は新しい重み y − x となります。 最終的に残る石は高々1つです。このとき、残った石の重みとして可能な最小値を求めてください（すべての石が消滅した場合は 0 とします）。 入力例と実行手順 たとえば入力が [2,7,4,1,8,1] の場合、出力は 1 になります

問題概要 文字列の部分列（subsequence）とは、元の文字列からいくつかの文字を削除することで得られる文字列です（削除なしでも構いません）。 source と target の2つの文字列が与えられたとき、target を作るために必要な source の部分列の最小個数を求めます。どうしても作れない場合は -1 を返します。 たとえば、source = abc、target = abcbc の場合、出力は 2 になります。 これは「abc」という部分列で最初の3文字をカバーし、続けて「bc」という部分列で残りの2文字をカバーできるためです。 アプローチ：貪欲法＋二分探索 この問題は、

問題の概要価格の配列 P = [p1, p2, ..., pn] と目標値(target)が与えられます。各価格 Pi を Floor(Pi)(切り捨て)または Ceil(Pi)(切り上げ)のどちらかで丸め、丸め後の配列 [Round1(P1), Round2(P2), ..., Roundn(Pn)] の合計がちょうど目標値になるようにしてください。どのような丸め方をしても合計を目標値にできない場合は、文字列 -1 を返します。達成できる場合は、丸め誤差の総和が最小となる値を返します。丸め誤差は次の式で定義され、小数点以下3桁の文字列として出力します。Σ |Roundi(Pi) − Pi|(

重複のない整数が昇順にソートされた配列Aが与えられたとき、配列の左端（先頭）の数を起点として、k番目に欠落している数を見つける問題を考えます。例えば、配列が [4, 7, 9, 10] で k = 1 の場合、4と7の間で最初に欠けている数は 5 となります。解法のアプローチ：二分探索この問題は、単純に1つずつ数えていく線形探索でも解けますが、配列がソートされていることを利用すると二分探索によって O(log n) の時間計算量で効率的に解くことができます。基本的な考え方は次の通りです。区間 [low, high] 内に存在するはずの数の個数は「nums[high] − nums[low] +

問題概要 同じ長さの2つの文字列 A と B が与えられ、各位置 i において A[i] と B[i] は「等価な文字」であると定義します。例えば、A = abc、B = cde の場合、「a」と「c」、「b」と「d」、「c」と「e」がそれぞれ等価であることを意味します。 この等価関係は、一般の同値関係と同じ性質を持ちます。 反射律: a = a(任意の文字は自分自身と等価) 対称律: a = b ならば b = a 推移律: a = b かつ b = c ならば a = c 例えば、上記の A と B の等価性情報をもとにすると、S = eed、acd、aab はすべて互いに等価な文字列

文字列Sが与えられたとき、その中に含まれる最も長く繰り返される部分文字列の長さを求めることを考えます。繰り返される部分文字列が存在しない場合は0を返します。例えば、文字列が「abbaba」の場合、出力は2になります。これは、最も長い繰り返し部分文字列が「ab」または「ba」（長さ2）であるためです。解法のアプローチ：動的計画法（DP）この問題は、動的計画法を用いて効率的に解くことができます。dp[i][j]を「位置iで終わる部分文字列と位置jで終わる部分文字列の共通接尾辞の長さ」と定義します。文字が一致するたびに、直前の状態に1を加えていくことで、繰り返し部分文字列の長さを段階的に求められます

文字列 S が単語のリストを表していると考えます。ここで、単語を構成する各文字には1つ以上の選択肢（オプション）が存在します。選択肢が1つだけの場合、その文字はそのまま記述されます。一方、複数の選択肢がある場合には、波括弧 { } によって選択肢が囲まれます。 たとえば、「{a,b,c}」という記述は選択肢「a」「b」「c」を表します。入力が「{a,b,c}d{e,f}」のような形式で与えられた場合、これは次の6つの単語からなるリストを意味します。 [ade, adf, bde, bdf, cde, cdf] 本記事では、このような形式の文字列から生成可能なすべての単語を列挙し、辞書順（lex

問題概要同じ長さを持つ2つの整数配列が与えられたとき、次の式の最大値を求めることを考えます。|arr1[i] − arr1[j]| + |arr2[i] − arr2[j]| + |i − j|ここで、最大値は 0 ≤ i, j < arr1.length を満たすすべての組み合わせについて評価します。たとえば、配列 [1,2,3,4] と [-1,4,5,6] が与えられた場合、答えは 13 になります。解法のアプローチすべての (i, j) の組み合わせを素朴に調べると計算量は O(n²) になりますが、絶対値を展開して式を整理すると O(n) で解くことができます。ポイントは、3つ

2つの文字列 text1 と text2 が与えられたとき、それらの最長共通部分列（Longest Common Subsequence：LCS）の長さを返す問題を考えてみましょう。部分列と共通部分列とは部分列（subsequence）とは、元の文字列から一部の文字を削除して作られる新しい文字列のことで、残りの文字の相対的な順序は変えません。たとえば「abe」は「abcde」の部分列ですが、「adc」は順序が崩れるため部分列ではありません。共通部分列とは、2つの文字列に共通して現れる部分列のことです。共通部分列が存在しない場合は 0 を返します。例として、入力が「abcde」と「ace」の場合

文字列 text が与えられ、その中の任意の2文字を一度だけ入れ替えることができるとします。このとき、同じ文字が連続して並ぶ最長の部分文字列の長さを求めるのが本記事のテーマです。 例えば、入力が「ababa」の場合、答えは 3 になります。先頭側の b と末尾の a を入れ替える(または末尾の b と先頭の a を入れ替える)ことで、「aaa」という繰り返し文字列が作れるため、その長さは 3 となります。 解法の考え方：スライディングウィンドウ この問題は、スライディングウィンドウ(尺取り法)を用いることで O(n) の計算量で効率的に解けます。ウィンドウ内に含まれる文字の種類を最大2種類に制

連結リストの先頭ノード（head）が与えられたとき、ノード値の合計が0になる連続したノード列を、そのような列が一切なくなるまで繰り返し削除し、最終的な連結リストの先頭を返すことを考えます。例えば、連結リストが [1, 2, -3, 3, 1] という構成の場合、「1 + 2 + (-3) = 0」となるため先頭の3ノードが削除され、答えは [3, 1] になります。 解決の手順 この問題は、プレフィックス和（累積和）とハッシュマップを組み合わせることで効率的に解くことができます。アルゴリズムの流れは以下の通りです。 値0を持つダミーノード（dummy）を作成し、dummy の next を

このチュートリアルでは、C++のSTL（標準テンプレートライブラリ）を活用したさまざまなマージ操作について解説します。 merge()関数は、ソート済みの2つのコンテナを1つに統合するための関数です。統合後の新しいコンテナも自動的にソートされた状態になります。一方、includes()関数は、あるソート済み範囲の要素がすべて別の範囲に含まれているかどうか（部分集合の関係にあるか）を判定するために使用されます。 merge()とincludes()の使用例 #include<iostream> #include<algorithm> #include<vector

本記事では、C++の演算子オーバーロードを活用して、vector・map・pair の中身を std::cout で手軽に出力する方法を解説します。演算子オーバーロードとは、既存の演算子に対してユーザー定義型向けの動作を定義できるC++の機能です。これにより、組み込み型と同じような自然な記述でオブジェクトを扱えるようになります。特にストリーム出力に使う << 演算子をオーバーロードしておけば、コンテナの中身を1行のコードで整形して表示でき、デバッグ作業が格段に楽になります。実装例1. vector の内容を出力するテンプレート関数として operator<< を定義すれ

このチュートリアルでは、C++におけるコンストラクタとデストラクタの呼び出し順序について、サンプルプログラムを通じて解説します。コンストラクタ／デストラクタの「呼び出し順序」とは、クラスの継承関係において、基底クラスと派生クラスそれぞれのコンストラクタやデストラクタがどのような順番で実行されるかを示すパターンのことです。この挙動を正しく理解することは、C++のオブジェクト指向プログラミングにおいて非常に重要な基礎知識となります。コンストラクタの呼び出し順序C++では、派生クラスのオブジェクトを生成すると、まず基底クラスのコンストラクタが呼び出され、その後に派生クラスのコンストラクタが呼び出され

本記事では、順序集合（ordered set）と GNU C++ PBDS（Policy-Based Data Structures）の基本的な使い方について解説します。 順序集合（ordered set）とは 順序集合は、STLライブラリには含まれていない「ポリシーベース構造」の一つです。すべての要素を常にソートされた状態で保持し、重複する値は許容しません。通常の std::set の機能に加えて、以下のような強力な操作を対数時間 O(log n) で実行できる点が最大の特徴です。 find_by_order(k)：ソート済みの集合の中でk番目（0始まり）の要素へのイテレータを返す ord

本記事では、C++における「出力イテレータ（Output Iterator）」の基本概念と使い方を、実際のサンプルコードとともにわかりやすく解説します。出力イテレータとはC++の標準ライブラリには、主に5種類のイテレータが存在し、出力イテレータはそのうちの1つです。出力イテレータは入力イテレータとは正反対の性質を持ち、コンテナへ値を書き込む（代入する）ことはできますが、格納された値を読み取ることはできません。代表的な出力イテレータとしては、std::ostream_iterator や std::back_insert_iterator などが挙げられます。サンプルコード#include<