Python

問題概要 文字列 s が与えられ、この文字列は任意の位置でちょうど1回だけ回転できるものとします。この操作を行った結果として得られる、最長の回文（パリンドローム）部分文字列の長さを求めるのが目的です。 たとえば、入力が s = elklev の場合を考えてみましょう。「el」と「klev」の間で回転すると「levelk」という文字列が得られます。このとき最長の回文部分文字列は「level」であり、その長さは 5 となります。 解法のアプローチ この問題は、以下の手順で解くことができます。 s2 := 文字列 s を2回連結した文字列を作る max_len := 0 で初期化する x を 0

問題の概要 小文字のみで構成された文字列 s が与えられたとき、すべての母音（a, e, i, o, u）がそれぞれ偶数回出現する最長の部分文字列の長さを求めることを考えます。 例えば、入力が s = anewcoffeepot の場合、出力は 10 になります。これは、部分文字列 wcoffeepot に含まれる母音が o と e の2種類であり、どちらも2回ずつ出現しているためです。 解法のアプローチ：ビットマスクとハッシュマップの活用 この問題は、ビットマスク（bitmask）とハッシュマップを組み合わせることで、O(n) の計算量で効率的に解くことができます。 基本的な考え方は次の通

数値 k と文字列 s が与えられたとき、最大で k 種類の異なる文字を含む最長の部分文字列（substring）の長さを求める問題について解説します。例えば、k = 3、s = kolkata が入力として与えられた場合、出力は 4 になります。これは、「kolk」と「kata」という2つの部分文字列がどちらも3種類の異なる文字を含み、その長さが4であるためです。解法のアプローチ：スライディングウィンドウこの問題は「スライディングウィンドウ（sliding window）」という手法を使うことで効率的に解けます。ウィンドウの右端を1つずつ進めながら、ウィンドウ内に含まれる異なる文字の種類数を

問題概要 1と−1という2つの値だけを含むリストが与えられたとき、要素の合計が0になる最長の部分リスト（連続する部分列）の長さを求めます。 例えば、入力が nums = [1, 1, -1, 1, 1, -1, 1, -1, 1, -1] の場合、出力は 8 になります。これは、最長の部分リストが [-1, 1, 1, -1, 1, -1, 1, -1] であり、その合計が0だからです。 解法のアプローチ：累積和と辞書 この問題は「累積和（プレフィックスサム）」を使うことで効率的に解けます。ある位置 i までの累積和が cs であるとき、同じ累積和の値が以前に位置 j で現れていれば、区間

問題の概要 リスト nums と整数 k が与えられたとき、連続する k 個の要素からなる各サブリスト（スライディングウィンドウ）ごとの最大値を求め、その結果をリストとして返すことを考えます。 例えば、nums = [12, 7, 3, 9, 10, 9]、k = 3 の場合、出力は [12, 9, 10, 10] になります。 これは、先頭から順に3要素ずつ区切った [12, 7, 3]、[7, 3, 9]、[3, 9, 10]、[9, 10, 9] のそれぞれの最大値を並べたものです。 解法の考え方 この問題は、現在の最大値とその位置を記録しながら窓をずらしていくことで解けます。具体的な

文字列 s が与えられたとき、末尾に文字を追加して回文にするために必要な最小の追加文字数を求める問題です。たとえば、入力が s = mad の場合、出力は 2 になります。これは、末尾に am を追加することで madam という回文を作れるためです。アプローチ：ローリングハッシュで最長の回文接尾辞を見つけるこの問題を効率的に解く鍵は、「文字列の末尾側に最も長く続く回文（回文接尾辞）」を見つけることです。s[i:] が回文であれば、先頭から i 文字分を逆順にして末尾に追加するだけで文字列全体を回文にできます。したがって、答えは「s[i:] が回文となる最小の i」と一致します。すべての接尾辞

互いに異なる単語のリストが与えられたとき、その中から2つの異なる単語を選んで連結し、回文（パリンドローム）を作ることができる組み合わせの総数を求める問題です。 例えば、入力が words = [time, emit, mo, m] の場合、「timeemit」「emittime」「mom」の3通りが作れるため、出力は 3 になります。 解法のアプローチ この問題は、以下の手順で解くことができます。 結果を格納する変数 res を 0 で初期化します。 ln に配列内の単語の個数を代入します。 k を 0 から 1 まで繰り返します。 i を 0 から ln − 1 まで繰り返します。

問題概要nums という数値のリストが与えられているとします。この数値同士の間に +、−、* などの二項演算子を挿入し、さらに有効な括弧を任意に追加することで構成できる式の中から、生成できる値の最大値を求めるのが課題です。たとえば、入力が nums = [-6, -4, -10] の場合、((-6) + (-4)) × (-10) という式を作ることができるため、出力は 100 となります。解き方（アルゴリズム）この問題は区間DP（インターバル・ダイナミックプログラミング）を用いて効率的に解けます。重要なポイントは、各区間について「最小値」と「最大値」の両方を記録することです。負の数同士を掛け

問題概要 同じ長さを持つ3つのリスト「deadlines（締め切り）」「credits（単位）」「durations（所要日数）」があるとします。これらは講義の課題に関する情報を表しています。i番目の課題については、deadlines[i]が締め切り日、credits[i]がその課題で得られる単位数、durations[i]が完了までにかかる日数を示します。 この問題には以下の制約があります。 1つの課題が完了してからでなければ、次の課題に取り掛かれない 締め切り当日に課題を完了することも可能 現在は0日目の始まりである 例えば、入力が deadlines = [7, 5, 10]、cre

隣接リスト形式でグラフが与えられているとします。このグラフは実際には、互いに連結していない複数の木から構成される「森（フォレスト）」です。ここで、いくつかの辺を追加して森全体を1本の木につなげることを考えます。その際、任意の2つのノード間の最長経路の距離（木の直径）が最小になるようにしなければなりません。 例えば、次のような入力が与えられた場合を考えてみます。 このとき、出力は 4 になります。 具体的には、ノード0とノード5の間に辺を追加すると、最長経路は「3 → 1 → 0 → 5 → 7」あるいは「4 → 1 → 0 → 5 → 7」（およびその逆方向の経路）のいずれかになります。し

問題の概要N × N の通貨レート表が与えられ、そこから一連の取引を実行できるかどうかを判定します。任意の通貨を金額 A からスタートし、最終的に同じ通貨で A より多い金額に戻せれば、裁定取引（アービトラージ）が成立していることになります。取引コストはなく、端数単位での取引も可能であると仮定します。この行列の [i, j] 成分は、「通貨 i を 1 単位売ったときに通貨 j をいくら購入できるか」を表します。ここでは、通貨 0 を米ドル（USD）、通貨 1 をカナダドル（CAD）、通貨 2 をユーロ（EUR）とします。アービトラージの具体例たとえば、次のような取引の連鎖によって裁定取引が可

2つの正の整数 n と d が与えられたとします。ここで、d は 0〜9 のいずれかの1桁の数字です。この課題では、1 から n までの整数の中に、数字 d が合計で何回出現するかを求めます。例えば、入力が n = 45、d = 5 の場合、出力は 5 となります。その理由は、1〜45 の範囲内で「5」という数字を含む数が以下の5つ存在するためです。[5, 15, 25, 35, 45]解法のアプローチこの問題は、全数を1つずつ調べるよりも、再帰的な計算によって効率よく求めることができます。手順は以下の通りです。関数 solve() を定義します。引数として n と d を受け取ります。n が

問題概要 隣接リスト形式で表された無向グラフが与えられます。graph[i] はノード i に隣接するノードの一覧を表します。このとき、次の条件を満たす辺の本数を求めます。 ある辺を取り除いたとき、グラフが非連結（分断された状態）になる。 このような辺は、グラフ理論では「橋（ブリッジ）」と呼ばれます。 たとえば、入力が次のような場合を考えてみましょう。 graph = [ [0, 2], [0, 4], [1, 2, 3], [0, 3, 4], [4], [3], [2] ] この場合、出力は 1 となります。ノード 4 はノード 3

問題概要 数値のリスト nums が与えられます。この中から、添字について a < b < c < d を満たし、かつ nums[a] < nums[b]（前半が昇順ペア）、nums[c] > nums[d]（後半が降順ペア）という条件を満たす4つ組 (a, b, c, d) の個数を求めます。 なお、配列 nums は 1〜N の整数の順列であることが保証されています。 入力例と出力例 入力が nums = [3, 4, 7, 6, 5] の場合、答えは 5 になります。 この入力から見つかる組み合わせは、以下の5通りです。 (3, 4, 7, 6) (3,

問題の概要 2つの数値リスト nums0 と nums1、および整数 k が与えられたとします。目標は、nums0 の要素1つと nums1 の要素1つから構成されるペアの中から、合計値が大きい方から k 個のペアを見つけ出し、それらの合計を返すことです。 例えば、入力が nums1 = [8, 6, 12]、nums2 = [4, 6, 8]、k = 2 の場合、出力は 38 になります。これは、最大のペアが [12, 8](合計20)と [12, 6](合計18)であり、20 + 18 = 38 となるためです。 解法のアプローチ この問題は、ヒープ(優先度付きキュー)を使うことで効率的

数値のリスト nums と整数 k が与えられたとき、「隣接する要素同士の絶対差がすべて k 以下」という条件を満たす最長の部分列(サブシーケンス)の長さを求める問題を考えてみましょう。 たとえば、入力が nums = [5, 6, 2, 1, -6, 0, -1]、k = 4 の場合、答えは 6 になります。 アプローチ：セグメント木による効率的な解法 この問題を素朴な動的計画法で解くと O(n²) の計算量が必要になり、要素数が多い場合には非効率です。そこでセグメント木(segment tree)を活用すると、各要素の処理を O(log n) に抑えられ、全体を O(n log n) で解

問題概要 負でない整数のリストと正の整数 k が与えられたとき、要素の合計が k で割り切れる 部分列の中から、合計が最大になるものを見つけることを考えます。 例えば、入力が次のような場合を考えてみましょう。 nums = [4, 6, 8, 2], k = 2 この場合の出力は 20 になります。リスト全体の合計は 20 であり、これは 2 で割り切れるためです。 解法のアプローチ 基本的な考え方はシンプルです。まず配列全体の合計を求め、それが k で割り切れない場合は、「合計を k で割った余りと同じ余りを持つ最小の部分集合」を取り除けばよい、という発想です。具体的には以下の手順で進めま

問題の概要 正の整数のリストが与えられているとします。ここで、「同じ値が連続する長さ t の部分リスト」を一度に取り除くことができ、その際に t × t のポイントを獲得できるものとします。この操作は、リストが空になるまで何度でも繰り返し行えます。求めたいのは、最適な順序で削除を行ったときに獲得できるポイントの最大値です。 たとえば、入力が nums = [4, 4, 6, 4, 4] の場合、出力は 17 になります。 この結果が得られる流れを見てみましょう。まず、長さ1の「6」を取り除いて 1 × 1 = 1 ポイントを獲得します。すると残りのリストは [4, 4, 4, 4] となり、こ

問題の概要バイナリ文字列 s と、2つの整数値 zero_one および one_zero が与えられます。このとき、次のような操作を任意の回数だけ実行できるものとします。部分文字列「01」を削除すると、zero_one ポイントを獲得できる部分文字列「10」を削除すると、one_zero ポイントを獲得できる操作を何度でも行える場合に、取得できるポイントの合計の最大値を求めるのがこの問題の目的です。たとえば、入力が s = 10100101、zero_one = 3、one_zero = 2 の場合、答えは 11 になります。「01」を3回削除して 3 × 3 = 9 ポイントを獲得し、残っ

問題概要数値のリスト nums と整数 k が与えられたとします。このリストを「連続する要素からなる」k個のグループに分割することを考えます。ここで「最小グループ」とは、各グループの合計値の中で最も小さいものを持つグループのことです。求めたいのは、その最小グループの合計値が取りうる最大値です。例として、nums = [2, 6, 4, 5, 8]、k = 3 の場合を見てみましょう。リストを [2, 6]、[4, 5]、[8] の3つのグループに分割すると、それぞれの合計は 8、9、8 となり、最小グループの合計は 8 になります。どのように分割しても最小グループの合計が 8 を超えることはで