C++

問題概要文字列の配列 A が与えられたとき、A に含まれるすべての文字列を部分文字列として持つ、最も短い文字列(スーパーストリング)を1つ求めることを考えます。ただし、A 内のどの文字列も、他の文字列の部分文字列ではないものと仮定できます。たとえば、入力が [dbsh, dsbbhs, hdsb, ssdb, bshdbsd] の場合、出力は hdsbbhssdbshdbsd となります。この問題は、文字列同士の重なり(オーバーラップ)を辺のコストとみなすことで、巡回セールスマン問題(TSP)とよく似た構造になり、ビットDP(動的計画法)を用いて効率的に解くことができます。アルゴリズムの考え方

問題の概要 互いに異なる正整数からなる配列 A が与えられたとします。ここで、次のようなグラフを考えてみましょう。 グラフのノード数は配列 A の長さと同じで、各ノードには A[0] から A[A のサイズ − 1] までのラベルが付いています。A[i] と A[j] が 1 より大きい共通の約数(公約数)を持つとき、A[i] と A[j] の間に辺が張られます。この課題では、グラフ内の最大連結成分のサイズを求めることが目標です。 たとえば、入力が [4, 6, 15, 35] の場合、出力は 4 になります。これは、4 と 6 が公約数 2 を、6 と 15 が公約数 3 を、15 と 35

ビルボードを設置する際、その高さはできるだけ高くしたいものです。ビルボードは両側に2本の鋼製の支柱で支えられますが、それぞれの支柱は必ず同じ高さでなければなりません。また、溶接によって自由に接合できる棒(ロッド)のコレクションが与えられます。たとえば、長さ1、2、3のロッドがあれば、これらをつなぎ合わせて長さ6の支柱を作ることができます。ここでの課題は、ビルボードを支えられる最大の高さを求めることです。もしビルボードを支えることができない場合は0を返します。 たとえば、入力が [1,2,2,3,3,3,4] の場合、出力は9になります。これは、ロッドを [1,2,2,4](合計9)と [3,

問題概要 小文字のアルファベットのみで構成され、長さがすべて同じ N 個の文字列からなる配列 A が与えられます。ここで、削除対象となる列(インデックス)の集合 D を自由に選び、各文字列からその位置の文字をすべて取り除くことを考えます。削除後の最終的な配列では、すべての行が次の条件を満たす必要があります。 A[0] の各文字が A[0][0] <= A[0][1] <= ... <= A[0][n - 1] と非降順に並んでおり、A[1] も同様に A[1][0] <= A[1][1] <= ... <= A[1][n - 1] となっている、という具合

問題の概要 正の整数 x が与えられ、「x (op1) x (op2) x (op3) x …」という形式の式を作ることを考えます。ここで op1、op2 などの各演算子には、加算（+）、減算（−）、乗算（*）、除算（/）のいずれかを使用できます。たとえば x = 3 のとき、「3 * 3 / 3 + 3 − 3」という式を書けば、その値は 3 になります。 式を組み立てる際には、次のルールが適用されます。 除算演算子（/）は有理数を返します。 括弧はどこにも置けません。 通常の演算の優先順位に従います。乗算と除算は、加算・減算よりも高い優先度を持ちます。 単項マイナス（負符号）は使用できま

問題の概要2つの文字列 S と T があるとします。それぞれ正の有理数を表しており、両者が同じ数値を表しているかどうかを判定するのが課題です。文字列では、有理数の循環小数部分（繰り返し部分）を括弧「( )」で示すことができます。ご存知のとおり、有理数は最大で3つの部分、すなわち「整数部分」「非循環部分」「循環部分」を使って表現できます。数値の表記は、次の3つの形式のいずれかになります。整数部分のみ（例：0、12、123）整数部分.非循環部分（例：0.5、1.0、2.12、2.0001）整数部分.非循環部分(循環部分)（例：0.1(6)、0.9(9)、0.00(1212)）たとえば、0.1(6)

問題の概要整数型の配列 A が与えられているとします。このとき、次の条件をすべて満たすインデックスのトリプル (i, j, k) の個数を求める必要があります。0 <= i < A のサイズ0 <= j < A のサイズ0 <= k < A のサイズそして、A[i] AND A[j] AND A[k] の計算結果が 0 になることです。ここでいう AND は、ビットごとの論理積（bitwise-AND）演算子を表します。たとえば、入力が [3, 1, 2] の場合、条件を満たすトリプルは合計 12 個存在するため、出力は 12 となります。解法のアプローチす

正の整数からなる配列Aがあるとします。連続する要素からなる部分配列（サブ配列）の中で、含まれる異なる整数の個数がちょうどK個であるものを「良い部分配列」と呼ぶことにします。例えば、配列 [1,2,3,1,2] には 1、2、3 という3つの異なる整数が含まれています。この記事では、配列Aに存在する「良い部分配列」の総数を求めるアルゴリズムを解説します。 問題の例 入力が [1,2,3,1,4]、K = 3 の場合を考えてみましょう。このとき出力は 4 になります。これは、異なる整数がちょうど3つ含まれる部分配列として、以下の4つが存在するためです。 [1,2,3] [1,2,3,1] [2

問題概要 0と1のみから構成される配列Aが与えられます。「Kビットフリップ」とは、長さKの連続する部分配列をひとつ選び、その範囲内のすべてのビットを同時に反転させる操作のことです。この操作を繰り返し、配列内に0が一つも残らない状態を目指します。必要となる最小のKビットフリップの回数を求めてください。ただし、どのように操作しても達成できない場合は -1 を返します。 入出力例 入力が [0,0,0,1,0,1,1,0]、K = 3 の場合、答えは 3 になります。次の手順で操作することで、すべての要素を1にできます。 1回目：A[0]〜A[2] をフリップ → 配列は [1,1,1,1,0,

問題概要 正整数からなる配列 A が与えられたとします。すべての隣接する 2 要素の和が完全平方数であるとき、この配列を「平方数配列（Squareful 配列）」と呼びます。求めたいのは、A を並べ替えて作られる順列のうち、平方数配列となっているものの総数です。なお、あるインデックス i において A1[i] ≠ A2[i] となるとき、またそのときに限り、2 つの順列 A1 と A2 は「異なる」ものとみなします。 たとえば、入力が [3, 30, 6] のとき、答えは 2 になります。[3, 6, 30] と [30, 6, 3] という 2 通りの順列が条件を満たすためです（3 + 6

問題概要 一列に並んだ N 個の石の山があり、i 番目の山には stones[i] 個の石が入っています。1 回の操作では、連続する K 個の山を 1 つの山にまとめることができ、このときのコストはその K 個の山に含まれる石の総数に等しくなります。 この問題では、すべての山を 1 つの山にまとめるための最小コストを求めます。なお、そもそも 1 つの山にまとめることが不可能な場合は -1 を返します。 具体例で確認 例えば、入力が [3, 2, 4, 1]、K = 2 の場合、出力は 20 になります。手順は以下の通りです。 初期状態：[3, 2, 4, 1] [3, 2] をコスト 5

問題の概要 正の整数 N が与えられたとき、N以下の正の整数の中に、少なくとも1つの重複した桁（同じ数字が2回以上現れる）を含む数がいくつあるかを求める問題です。 例として、入力が 99 の場合を考えてみましょう。このときの出力は 9 となります。該当するのは 11, 22, 33, 44, 55, 66, 77, 88, 99 の9個だからです。 解法のアプローチ すべての数を1つずつ確認するのは非効率です。そこで視点を変え、「重複した桁を一切含まない数」の個数を組み合わせ論的に数え上げ、それを N から引くことで高速に答えを得られます。 具体的には、次の手順で進めます。 関数 A(m,

文字が順次入力されるストリームの中で、直近の文字列が指定した単語リストに含まれるかどうかを即座に判定したい場面はよくあります。本記事では、C++でトライ木（Trie）を用いてこのような StreamChecker クラスを実装する方法を解説します。 問題の概要 次のような StreamChecker クラスを実装することを考えます。 StreamChecker(words) − コンストラクタです。与えられた単語リストでデータ構造を初期化します。 query(letter) − ある k ≥ 1 に対して、これまでに照会された最後の k 文字（今回照会した文字を含み、古いものから新しいものへ

問題の概要文字列 S が与えられます。ここで、S の中に 2 回以上出現する連続する部分文字列（重複部分文字列）をすべて考えてみましょう。ただし、出現位置が互いに重なっても構いません。このとき、最も長い重複部分文字列を見つけるのが課題です。該当する部分文字列が存在しない場合は空文字列を返します。なお、ローリングハッシュによる計算では値が巨大になるため、109 + 7 を法（mod）として演算を行います。例えば、入力が "ababbaba" の場合、出力は "bab" となります。解き方のアプローチこの問題は、二分探索とローリングハッシュ（Rabin–Ka

問題概要行列(matrix)とターゲット値(target)が与えられたとき、要素の合計がターゲットと一致する空でない部分行列がいくつ存在するかを求める問題です。ここで部分行列 [(x1, y1), (x2, y2)] とは、x が x1 以上 x2 以下、y が y1 以上 y2 以下の範囲に含まれるすべてのセル matrix[x][y] の集合を指します。また、2つの部分行列 [(x1, y1), (x2, y2)] と [(x1, y1), (x2, y2)] は、座標が1つでも異なれば別のものとして扱われます(例えば x1 ≠ x1 の場合など)。入力例010111010このとき tar

2つの文字列 str1 と str2 が与えられたとき、その両方を部分列として含む最短の文字列（最短共通スーパーシーケンス）を求める問題を考えます。答えが複数存在する場合は、そのうちの1つを返せばよいことになっています。ここで、文字列 S が文字列 T の部分列であるとは、T からいくつかの文字（0個でも可）を任意の位置から削除した結果が S と一致することを指します。例えば、入力が acab と bac の場合、出力は bacab となります。これは、与えられた2つの文字列がどちらも bacab の部分列になっているためです。アルゴリズムの考え方この問題は、まず最長共通部分列（LCS: Lo

文字列 s が与えられたとき、辞書式順序で最も大きい(最後の)部分文字列を求める問題を考えます。 例えば、入力が abbbcabbc の場合、出力は cabbc となります。 すべての部分文字列を総当たりで比較すると計算量が膨大になりますが、2つのポインタ(i と j)と比較位置を示す変数 k を使うことで、線形時間 O(n) で効率的に解くことができます。 重要な性質 辞書式順序で最大の部分文字列は、必ずある位置から始まり末尾まで続く接尾辞になります。これは、部分文字列を後ろに伸ばしても辞書式順序が小さくなることはないためです。したがって、この問題は「最適な開始位置を見つける問題」として

整数を格納する2つの配列 arr1 と arr2 が与えられているとします。ここでの目的は、arr1 を厳密に増加する(狭義単調増加の)配列にするために必要な最小の操作回数を求めることです。なお「操作」とは、インデックス i(0 ≤ i < n)と j(0 ≤ j < m)を選び、arr1[i] = arr2[j] という代入を行うことを指します(n と m はそれぞれ arr1 と arr2 のサイズです)。 どのように操作しても arr1 を厳密に増加させることができない場合は、-1 を返します。 例えば、入力が arr1 = [1,5,3,7,8]、arr2 = [1,3,2

n台のサーバーがあり、それぞれ0からn-1までの番号が付けられているとします。これらのサーバーは無向の接続によってネットワークを形成しており、connections[i] = [a, b] はサーバーaとサーバーbの間の接続を表します。すべてのサーバーは、直接または他のサーバーを経由して相互に到達できる状態になっています。ここで「重要な接続(クリティカルコネクション)」とは、その接続を取り除いたときに、あるサーバーから別のサーバーへ到達できなくなるような接続のことです。本記事では、このような重要な接続をすべて見つける方法を解説します。問題例例として、入力が n = 4、connections

問題概要 整数 n が与えられたとき、次のルールに従って構成できる長さ n の文字列が何通りあるかを数えます。 使用できるのは小文字の母音（a, e, i, o, u）のみ a の後ろには e のみ続けられる e の後ろには a または i のみ続けられる i の後ろに i は続けられない o の後ろには i または u のみ続けられる u の後ろには a のみ続けられる 答えは非常に大きな値になる可能性があるため、109 + 7 で割った余りを求めます。 入力例と出力例 たとえば入力が 2 の場合、出力は 10 となります。条件を満たす文字列は次の 10 通りだからです。 ae, ea