Python

問題概要 赤(R)、緑(G)、青(B)の3種類の色からなるリストを考えます。隣り合う異なる2つの色は、残りの「第3の色」1個に変換(マージ)できます。この変換を好きな順序で何度でも繰り返してよいとき、最終的に残る要素数の最小値を求めるのがこの問題です。 たとえば入力が colors = [G, R, G, B, R] の場合、次のように変換を進めることで最終的に1個まで減らせます。したがって出力は 1 となります。 解き方のアプローチ 一見すると状態探索が必要そうな問題ですが、実はXOR(排他的論理和)を使ったシンプルな判定だけで答えが求まります。手順は以下の通りです。 n := 色リス

ソートされた整数リスト stones が与えられ、これは渡ろうとしている川に置かれた石の位置を表しているとします。川を渡り切るためには、必ず最後の石までたどり着かなければなりません。各ステップでは、直前のジャンプ距離を k としたとき、(k − 1, k, k + 1) のいずれかの距離だけ前へジャンプすることができます。この条件のもとで、川を渡ることが可能かどうかを判定するのが本問題です。 問題の例 たとえば入力が stones = [0, 1, 3, 4, 5, 6, 8, 9, 13] の場合、答えは True になります。位置 0 からスタートし、まず 1 単位ジャンプして石 1 へ

問題の概要 0と1だけで構成される2進文字列が与えられ、任意の2つのビットを入れ替える（スワップする）ことができるとします。このとき、すべての「1」を連続した一つのグループにまとめるために必要な最小スワップ回数を求めるのが目的です。 例えば、入力が s = 0111001 の場合、出力は 1 になります。次のように、たった1回のスワップで達成できるからです。 0111001 → 1111000 解法のアプローチ：スライディングウィンドウ この問題は「スライディングウィンドウ」の考え方を使うと効率的に解けます。ポイントは次の通りです。 まず文字列中の「1」の総数を数えます。これを one と

問題の概要同じ長さを持つ2つの数値リスト nums0 と nums1、および距離を表す d と切り替えコストを表す c の2つの値が与えられているとします。私たちはどちらかのリストのインデックス0からスタートし、どちらかのリストの最終インデックスに到達することを目標とします。各ターンでは、次の2つの操作が可能です。コスト c を支払って、もう一方のリストに切り替える最大 d だけ前方へジャンプする(着地したインデックスの値がその分のコストとして加算される)このとき、タスクを完了するために必要な合計コストの最小値を求める必要があります。入力例nums0 = [2, 3, 10, 10, 6]nu

数値のリスト nums と整数 k が与えられたとき、「厳密に増加する」サイズ k の部分列(サブシーケンス)が何個存在するかを求めます。答えが非常に大きくなる可能性があるため、10^9 + 7 で割った余りを返します。たとえば、nums = [2, 3, 4, 1]、k = 2 の場合、出力は 3 になります。これは、サイズ 2 の増加部分列として [2, 3]、[3, 4]、[2, 4] の 3 つが存在するためです。解法のアプローチこの問題は動的計画法(DP)を用いて効率的に解くことができます。dp[j] は「インデックス j の要素を末尾とする、現在の長さの増加部分列の個数」を表し、各

問題の概要 各要素が [start（開始時刻）, end（終了時刻）, profit（利益）] の3つの値を持つ区間（ジョブ）のリストがあるとします。同時に実行できるタスクは1つだけという制約のもとで、得られる最大の利益を求めるのがこの問題の目的です。 例えば、入力が以下の場合を考えてみましょう。 intervals = [[1, 2, 100], [3, 5, 40], [6, 19, 150], [2, 100, 250]] この場合の出力は 350 になります。なぜなら、[1, 2, 100] と [2, 100, 250] の2つの区間を選ぶことで、100 + 250 = 350 と

問題の概要数値のリスト nums と整数 k が与えられたとき、サイズがちょうど k となる「辞書式順序で最小」の部分列（サブシーケンス）を求めることを考えます。ここで部分列とは、元のリストから要素を選び、元の順序を保ったまま並べたものを指します。例として、nums = [2, 3, 1, 10, 3, 4]、k = 3 の場合を考えてみましょう。このとき出力は [1, 3, 4] となります。サイズ3の部分列の中で、この並びが最も辞書式に小さいためです。解法のアプローチこの問題は貪欲法（グリーディ法）で解くことができます。手順は以下のとおりです。最初の要素は、リストの先頭から n−k 番目ま

数値リスト nums と整数 k が与えられたとき、連続する部分リスト(サブリスト)に含まれる一意な要素がちょうど k 個であるものの総数を求める問題です。 たとえば、入力が nums = [2, 2, 3, 4]、k = 2 の場合、条件を満たすサブリストは [2, 2, 3]、[2, 3]、[3, 4] の3つなので、出力は 3 になります。 解法のアプローチ:スライディングウィンドウ この問題は「スライディングウィンドウ(尺取り法)」を使うと O(n) で効率的に解けます。ポイントは、「ちょうど k 個」のサブリストを直接数えるのではなく、「一意な要素が最大 k 個以下のサブリストの数」

N × M の2値行列を考えます。ここで、0は空きセル（通過可能）、1はブロックされたセル（通過不可）を表します。左上の角からスタートして、右下の角に到達するまでの移動方法が何通りあるかを求めます。答えが非常に大きくなる場合は、10^9 + 7 で剰余を取ります。例えば、入力が以下のような行列だったとします。001000110この場合の出力は 2 になります。右下に到達できる経路は「右 → 下 → 右 → 下」と「下 → 右 → 右 → 下」の2通りしかないためです。解法のアプローチ：動的計画法（DP）この問題は、動的計画法（Dynamic Programming）を使うことで効率的に解けます

二分木が与えられたとき、その中から「二分探索木（BST）」として成立する最大の部分木（ノード数が最大のもの）を見つける問題を考えてみましょう。問題の概要例えば、次のような二分木が入力として与えられた場合を想定します。このとき、出力は以下のようになります。解法のアプローチこの問題を解くためには、以下の手順に従います。max_size := [0]、max_node := [null] を初期化する関数 traverse() を定義する。引数は nodenode が null の場合は null を返すleft := traverse(node の左の子)、right := traverse(no

問題概要 数値のリスト nums と整数 k が与えられたとき、リストの中からサイズ k の重複しない(オーバーラップしない)3つのサブリストを選び、その合計の最大値を求める問題です。 例えば、nums = [2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3]、k = 3 の場合、出力は 27 になります。これは、サブリストとして [2, 2, 2]、[4, 4, 4]、[3, 3, 3] を選択でき、その合計が 6 + 12 + 9 = 27 となるためです。 解法のアプローチ この問題は、累積和(プレフィックスサム)と前後からの最大値の記録を組み合わせることで、効率的に

問題の概要 数値のリスト nums と別の値 k が与えられたとき、リストを「各サブリストの長さが k 以上」かつ「厳密に増加している(昇順)」という条件を満たすサブリスト群に分割できるかどうかを判定します。なお、分割後のサブリストは元のリスト内で連続した範囲である必要はありません。 例えば、nums = [6, 7, 5, 10, 13]、k = 2 の場合、出力は True になります。これは、リストを [5, 6] と [7, 10, 13] の2つのサブリストに分割でき、どちらも長さが2以上かつ厳密に増加しているためです。 解法のアプローチ この問題は、各値の出現回数に着目することで効

問題の概要 非減少順（昇順）にソートされた数値リスト nums が与えられます。このリストを任意の個数の部分列に分割できるかどうかを判定してください。ただし、各部分列は最小長3以上であり、かつ連続的に増加している必要があります。 たとえば、入力が nums = [2, 3, 4, 4, 5, 6, 7] の場合、出力は True になります。これは、リストを [2, 3, 4] と [4, 5, 6, 7] という2つの部分列に分割でき、どちらも条件を満たすためです。 解法の考え方 この問題のポイントは、各値 x について「x から始まる部分列の数」と「x で終わる部分列の数」を求めることです

問題概要 数値のリスト nums が与えられたとき、「隣り合う2つの要素の差が正・負と交互に入れ替わる」ような最長の部分列（サブシーケンス）の長さを求めることを考えます。なお、最初の差が正から始まっても負から始まっても構いません。 たとえば入力が nums = [6, 10, 4, 2, 3, 9, 4, 7] の場合、答えは 6 になります。これは [6, 10, 2, 9, 4, 7] という部分列を選ぶと、その差が [4, -8, 7, -5, 3] となり、正と負がきれいに交互に現れるためです。 解決の手順（動的計画法） この問題は動的計画法（DP）を使うと効率よく解けます。各インデ

問題の概要数値のリスト nums が与えられたとき、そこから取り出せる「最長の等差数列（算術サブシーケンス）」の長さを求めます。ある数列 S が等差数列であるとは、すべての i（0 ≤ i < Sの長さ − 1）に対して、隣接する2項の差 S[i+1] − S[i] が常に同じ値になることを意味します。たとえば、入力が nums = [1, 4, 7, 10, 13, 20, 16] の場合、答えは 6 になります。これは、部分列 [1, 4, 7, 10, 13, 16] を選ぶと、隣接する要素同士の差がすべて 3 で一定だからです。解法のアプローチ：動的計画法（DP）この問題は動的計

問題概要3つの文字列 s1、s2、s3 が与えられたとき、これらすべてに共通する最長共通部分列（LCS：Longest Common Subsequence）の長さを求めることを考えます。たとえば、入力が以下のような場合を想定してみましょう。s1 = ababchemxdes2 = pyakcimdes3 = oauctimeこの場合の出力は 4 になります。これは、3つの文字列すべてに共通する最長の部分列が acme であり、その長さが4文字だからです。解き方（アルゴリズム）この問題は動的計画法（DP）を用いて効率的に解くことができます。2つの文字列に対するLCSの考え方を、3次元のDPテー

問題の概要二分木（バイナリツリー）が与えられたとき、ノード値の合計が偶数になる最長パスの長さを求めることを考えます。例えば、次のような木構造が入力として与えられた場合、出力は 5 になります。これはパス [5, 2, 4, 8, 5] を通ったときの合計が 24（偶数）となるためです。解法のアプローチ：DFS（深さ優先探索）この問題は、DFSを用いて各ノードから下方向に伸びる「偶数和のパス」と「奇数和のパス」の長さを同時に追跡することで解けます。dfs() 関数はペア (left_0, left_1) を返し、それぞれ「そのノードから下に伸びる合計が偶数のパスの最大長」「合計が奇数のパスの最大

2次元の行列が与えられたとき、その中に存在する「最も長い狭義単調増加パス」の長さを求める問題を考えます。パスをたどる際には、上下左右の4方向へ移動できますが、斜め方向への移動は許されません。例として、次のような入力行列を見てみましょう。246157339この場合の出力は 6 になります。最長のパスは [1, 2, 4, 6, 7, 9] となるためです。解法のアプローチこの問題は、深さ優先探索(DFS)による再帰を使って解くことができます。各マスを起点とした場合の最長増加パスの長さを計算し、その最大値を答えとします。具体的な手順は以下の通りです。行列の行数 n と列数 m を取得します。上下左

問題概要小文字のみで構成された文字列 s が与えられます。この文字列から文字を順番を崩さずに選んで作れる、最長の回文部分列（パリンドロームサブシーケンス）の長さを求めましょう。例えば、入力が s = aolpeuvekyl の場合、出力は 5 となります。これは、l・e・v・e・l を順に選ぶことで回文 level が構成できるためです。解法のアプローチこの問題は、区間を対象とした再帰的な動的計画法で解くことができます。区間 [i, j] における最長回文部分列の長さを dp(i, j) として定義し、以下の手順に従って計算します。n := 文字列 s のサイズとする関数 dp() を定義する

DAGの最長パス問題とは 隣接リスト形式で表された有向非巡回グラフ(DAG: Directed Acyclic Graph)が与えられたとき、同じノードを2度通らずに辿れる最長パスの長さを求める問題を考えます。 例として、次のようなグラフを想定してみましょう。 この場合、パス「0 → 1 → 3 → 4 → 2」が最長となるため、出力は 4 になります。 解法のアプローチ:DFSとメモ化の組み合わせ この問題は、深さ優先探索(DFS)にメモ化(結果のキャッシュ)を組み合わせることで効率的に解けます。各ノードから始まる最長パスの長さを一度計算したら結果を保存し、同じ計算を繰り返さないのがポイ