Python

文字列 s と、s の部分列（サブシーケンス）となっている別の文字列 t が与えられます。求めたいのは、削除した後も t が s の部分列であり続けるような、削除可能な部分文字列の長さの最大値です。 たとえば、入力が s = xyzxyxz、t = yz の場合、出力は 4 になります。先頭の4文字 xyzx を削除しても、残った文字列には依然として yz が部分列として含まれているためです。 解法のアプローチ この問題は貪欲法（グリーディ法）を使うことで効率的に解けます。ポイントは、次の3つの候補を調べることです。 c1（末尾側の削除）：左から貪欲に t をマッチングさせ、最後の文字が一致

問題概要数値のリスト nums と、各クエリが [x, limit] の形式を持つクエリリスト queries が与えられます。各クエリに対して、nums の中から limit 以下の要素 e を探し、e XOR x が最大になるような e を求めます。条件を満たす要素が存在しない場合は -1 を返します。例えば、nums = [3, 5, 9]、queries = [[4, 6], [2, 0]] の場合、出力は [3, -1] となります。最初のクエリでは、6以下の要素として 3 と 5 が候補になります。3 XOR 4 = 7、5 XOR 4 = 1 なので、より大きなXOR値を返す 3

この記事では、重なり合わない（非オーバーラップの）区間リストに対して、新しいターゲット区間を挿入・マージし、結果として得られる区間リストも依然として重複がなくソート済みである状態を保つアルゴリズムを、Pythonで実装する方法を解説します。 問題の概要 前提条件として、与えられる区間のリストは以下の性質を持ちます。 各区間は互いに重なっていない（non-overlapping） 終了時刻に基づいてソートされている ここに新たな区間 target が与えられたとき、target を既存の区間と適切にマージし、最終的な区間リストを求めます。マージ後もリストは「重複なし・ソート済み」の状態を維持

問題の概要 4×4の文字ボードと単語のリストが与えられたとします。このとき、隣接する文字を順にたどることで、ボード上から生成できる単語の最大数を求める必要があります。1つの単語を作る際には同じマスを最大1回しか使用できませんが、異なる単語同士であればマスを再利用しても構いません。移動は上下左右に加え、斜め方向も含めた8方向が可能です。 入力例 mbfdxayatztrsqqq words = [bat, far, mat] の場合、出力は 3 となります。これは、それぞれの単語を次の経路で生成できるためです。 mat: [0,1] → [1,1] → [2,0] bat: [0,2] →

問題の概要 数値のリスト nums が与えられたとき、nums[i] ≤ nums[j] を満たす2つの数値について、nums 内に (nums[i], nums[j]) の間に該当する数が存在しない場合、この2つの数値は「隣接している」とみなします。ここでの課題は、nums[j] と nums[i] が隣接関係にあるとき、そのインデックス差 |j − i| の最小値を求めることです。 たとえば、入力が nums = [1, -9, 6, -6, 2] の場合、出力は 2 になります。これは、値 2 と 6 が隣接しており、それぞれのインデックスが 2 つ離れているためです。 解決のためのア

文字列 s が与えられたとき、隣接する文字を入れ替える操作（スワップ）を何回行えば回文にできるか、その最小回数を求める問題を考えます。どのように操作しても回文にできない場合は -1 を返します。 たとえば、入力が s = xxyy の場合、答えは 2 になります。まず中央付近の「x」と「y」を入れ替えて xyxy とし、続いて先頭の2文字「x」と「y」を入れ替えて yxxy にすれば、これは回文となるからです。 回文にできるかどうかの判定方法 文字列を回文にできる条件は、「奇数回出現する文字が高々1種類であること」です。この条件をチェックする補助関数 util() を、以下の手順で実装します。

2つの文字列 s と t が与えられたとき、s の中から t のすべての文字を含む最小の部分文字列（substring）の長さを求めます。該当する部分文字列が存在しない場合は -1 を返します。 たとえば、s = "thegrumpywizardmakes"、t = "wake" とすると、出力は 10 になります。「w」「a」「k」「e」の4文字をすべて含む最短の部分文字列は "wizardmake"（長さ10）であるためです。 解き方のアプローチ：スライディングウィンドウ法 この問題は、左右2つのポインタでウィンドウを伸縮させな

問題の概要数字のみで構成された2つの文字列 s と t が与えられたとします。それぞれの文字列からいくつかの数字を削除し、以下の条件を満たすようにします。2つの文字列が同一になること削除した数字の合計が最小になることそして、その最小化された合計値を返すのが目的です。例えば、入力が s = 41272、t = 172 の場合、出力は 6 になります。これは、最初の文字列から「4」と「2」を削除すれば「172」に一致させることができ、削除した数字の合計は 4 + 2 = 6 となるためです。解決のアプローチ：LCS(最長共通部分列)の応用この問題は、動的計画法(DP)による最長共通部分列(LCS)

1次元の直線上にある家の位置を表す数値リスト nums が与えられているとします。ここで、3つの街灯を直線上の任意の位置に設置でき、位置 x にある街灯は範囲 [x − r, x + r]（両端を含む）内のすべての家を照らせるものとします。このとき、すべての家を照らすために必要な最小の半径 r を求めます。たとえば、入力が nums = [4, 5, 6, 7] の場合、出力は 0.5 になります。街灯を 4.5、5.5、6.5 の位置に配置すれば r = 0.5 となり、この3つの街灯ですべての4軒の家を照らすことができます。解法のアプローチこの問題は二分探索と貪欲法を組み合わせることで効率

問題の概要0と1のみで構成された数値のリスト nums と、整数 k が与えられます。ここで、「長さkの部分リスト(サブリスト)を選んで反転する」という操作を考えます。反転を行うと、その範囲内のすべての1は0に、0は1に変わります。この操作を繰り返して、リスト内のすべての1を0にするために必要な最小の操作回数を求めてください。どのように操作してもすべてを0にできない場合は -1 を返します。例えば、nums = [1,1,1,0,0,1,1,1]、k = 3 の場合、出力は 2 になります。これは、先頭の3つの要素を反転して0にし、次に末尾の3つの要素を反転して0にできるためです。解法のアプロ

問題の概要2進文字列 s が与えられているとします。この文字列に対しては、任意の接頭辞（先頭部分）を取り出して末尾へ移動するという操作が可能です。そのうえで、「隣り合う文字が同じ値にならないようにする」ために必要な最小の反転（フリップ）回数を求めるのがこの問題の目的です。たとえば、入力が s = 10010101111 の場合を考えてみましょう。まず接頭辞「10」を末尾に移動すると、文字列は「01010111110」になります。さらに、右から3番目と5番目のビットを0に反転すれば「01010101010」となり、0と1が交互に並んだ状態が完成します。したがって、このケースの出力は 2 となりま

問題の概要文字列 s は、いくつかの動物の初期状態を表しています。各動物は次の3種類のいずれかの値を取ります。L: 動物が左へ移動することを表しますR: 動物が右へ移動することを表します@: 動物がその場に静止していることを表しますある方向へ移動中の動物は、進行方向にある他の動物を押し流しながら移動していきます。ただし、反対方向から同じタイミングで力を受けると、その場で静止します。すべての動物が停止したときの、それぞれの最終的な向きを求めるのがこの問題の目的です。たとえば、入力が s = "@@L@R@@@@L" の場合、出力は "LLL@RRRLLL"

この記事では、Pythonを使って「容量」と「個数」の2つの制約を持つナップサック問題（0/1 Knapsack問題の拡張版）を解き、バッグに入れられるアイテムから得られる価値の最大値を求めるプログラムを紹介します。 問題の概要 同じ長さを持つ2つの数値リスト weights（重さ）と values（価値）、そして2つの数値 capacity（許容重量）と count（最大個数）が与えられます。weights[i] と values[i] は、i番目のアイテムの重さと価値を表します。 持ち運べるのは合計で最大 capacity の重さまで、かつ最大 count 個までのアイテムです。また、各ア

文字列 s が与えられます。この文字列は開き括弧「(」と閉じ括弧「)」のみで構成されています。ここで求めたいのは、最も長い有効（整形式）な括弧の部分文字列の長さです。例えば、入力が )(())()) の場合、最も長い有効な部分文字列は (())() であるため、結果は 6 となります。アルゴリズムの考え方：スタックを活用するこの問題は、スタックを使うことで効率的に解くことができます。基本的なアイデアは、括弧の対応関係をスタックで管理し、マッチするたびに現在位置との差分から有効な長さを計算するというものです。解法の手順スタックを作成し、初期値として -1 を挿入します。また、答えを格納する変数

Nクイーン問題とは0が空きマス、1がそのマスに配置されたチェスのクイーンを表す2値行列(バイナリマトリックス)が与えられているとします。この盤面を完成させ、有効なNクイーンの解が得られるかどうかを判定するのが本記事の目的です。ご存知の通り、Nクイーンパズルとは、n × n のチェス盤上に n 個のクイーンを、どの2つのクイーンも互いに攻撃し合わないように配置するという古典的な組合せ最適化問題です。例として、次のような入力が与えられた場合を考えます。1000000000000010000000010この場合、出力は True になります。既に置かれた3つのクイーンを動かさずに、残りのマスを埋める

本記事では、Pythonを使って「少なくともk個の奇数を含む最長増加部分列（LIS: Longest Increasing Subsequence）」の長さを求める方法を解説します。 問題の概要 数値のリスト nums と整数 k が与えられたとき、奇数がk個以上含まれる増加部分列の中で最も長いもののサイズを求めます。 例： 入力：nums = [12, 14, 16, 5, 7, 8]、k = 2 出力：3 この場合、奇数を2つ以上含む最長の増加部分列は [5, 7, 8] であり、その長さは3となります。 解法のアプローチ この問題は、再帰的な動的計画法（メモ化なしの全探索型DP）を用

問題の概要N個の正の数からなるリスト nums が与えられていると仮定します。このリストから任意の1つの値を選び、それを(スワップではなく)移動させて好きな位置に挿入することができます。もちろん、どの要素も移動しないという選択も可能です。このとき、リストのパワーが取りうる最大値を求めるのがこの問題です。ここでいうリストのパワーとは、すべてのインデックス i における (i + 1) × list[i] の総和として定義されます。$$\displaystyle\sum\limits_{i=0}^{n-1} (i+1)\times list[i]$$具体例入力が nums = [6, 2, 3]

問題の概要N本のフェンスを一列に並べ、K種類の異なる色で塗ることを考えます。ただし「隣り合うフェンス同士は同じ色にできない」という制約があり、そのうえで総コストを最小化したいのです。入力として N × K の行列が与えられます。n 行 k 列目の値は「n 番目のフェンスを k 番目の色で塗るときのコスト」を表します。このとき、制約を満たす塗り方の中で最小となる総コストを求めます。たとえば、次のような入力が与えられたとします。645327345544この場合の出力は 14 になります。最初のフェンスから順に、コスト 5 → 2 → 3 → 4 の色を選べば、隣接するフェンスの色が重ならず、合計コ

問題の概要 0と1のみで構成される2次元のバイナリ行列と、ある値 k が与えられます。左上のセルからスタートし、右下のセルへ向かいます。1回の移動で進めるのは「下」または「右」のいずれか一方のみです。パスのスコアは、そのパスが通過するセルの値の合計として定義されます。このとき、開始セルから終了セルまでのパスの中で、スコアがちょうど k に等しくなるものの総数を求めます。パスの候補数が非常に大きくなる可能性があるため、その場合は結果を 109+7 で割った余りを返すこととします。 入力例 001 101 010 k = 2 の場合、出力は 4 になります。スコアが 2 となるパスは [

問題の概要 小文字の英字のみで構成された文字列 s が与えられたとします。この文字列を、どの文字も複数の部分にまたがって出現しないという条件を満たすように、できるだけ多くの部分（パーティション）に分割し、それぞれの部分の長さをリストとして求めます。 たとえば、入力が s = momoplaykae の場合、文字列は [momo, p, l, ayka, e] の5つに分割できます。「m」は最初の部分に、「a」は4番目の部分にのみ含まれており、すべての文字が1つの部分に収まっているため条件を満たしています。よって出力は [4, 1, 1, 4, 1] となります。 解法のアプローチ この問題は