Python

問題概要単語のリスト words と文字列 s が与えられます。このとき、words に含まれる文字列のうち、s の部分列（サブシーケンス）になっているものの個数を求めるのが目標です。ここで「部分列」とは、元の文字列から一部の文字を削除して（文字の並び順は変えずに）得られる文字列のことを指します。たとえば、words = [xz, xw, y]、s = xyz という入力の場合、「xz」と「y」はどちらも「xyz」の部分列であるため、答えは 2 になります。解法のアプローチ各単語ごとに s を何度も走査すると非効率です。そこで、先頭文字ごとに単語をバケット（グループ）に分けて管理するのがポイン

問題概要各ノードが0〜9までの一桁の数字を持つ二分木を考えます。ルートから葉へと辿る各パスは、通過したノードの数字を順番につなげた一つの数値を表します。この記事では、木の中のすべてのパスが表す数値の合計を求めるPythonプログラムを解説します。具体例例として、次のような二分木を入力とした場合を考えます。この木には次の3つのパスが存在します。46（4 → 6）432（4 → 3 → 2）435（4 → 3 → 5）これらの合計は 46 + 432 + 435 = 913 となるため、出力は913になります。解法のアプローチこの問題は、深さ優先探索（DFS）を再帰的に行うことで解決できます。手順

問題の概要0と1のみで構成された2次元のバイナリ行列を考えます。ここで「1」は陸地、「0」は水を表します。島とは、隣り合った1の集まりであり、その周囲がすべて水で囲まれている領域のことです。本記事では、行列の中から端(境界)に一切接しておらず、完全に水で囲まれた島の数を数えるプログラムをPythonで実装する方法を解説します。例として、次のような入力が与えられた場合を考えてみましょう。この場合の出力は 2 となります。島は全部で3つ存在しますが、そのうち2つだけが完全に水で囲まれているためです。解法のアプローチ:DFS(深さ優先探索)この問題は、DFS(深さ優先探索)を用いることで効率的に解く

問題の概要部屋にn個のスイッチがあり、最初はすべてオフになっています。ここにn人の人が順番に現れ、次のルールでスイッチを切り替えていきます。1番目の人は、1の倍数であるすべてのスイッチ（つまり全スイッチ）を切り替える。2番目の人は、2の倍数であるスイッチ（2、4、6、…）を切り替える。i番目の人は、iの倍数であるスイッチを切り替える。このとき、最終的にオンになっているスイッチの数を求めるのがこの問題の目的です。具体例：n = 5 の場合入力が n = 5 のとき、出力は 2 になります。実際の動きを順に確認してみましょう（初期状態はすべてオフ）。初期状態：[0, 0, 0, 0, 0]1番目の

問題の概要文字列のリスト votes が与えられます。各要素は小文字のみで構成され、候補者への投票を「最も優先度が高い順位から低い順位へ」の順に表しています。候補者の順位は、まず第1優先として受け取った票数で決まります。ここで同点が発生した場合は、次に高い優先度での得票数を比較し、それでも決まらない場合はアルファベット順で順位を確定します。このルールに基づき、チーム（候補者）の最終ランキングを上位から下位の順に出力します。入力例と考え方たとえば votes = [zyx, zxy, xyz] の場合、出力は zxy になります。「z」は第1優先の票を最も多く獲得したため1位。「x」は第1優先の

各ノードの値がそのノードの色を表す二分木を考えます。木に含まれる色は最大で2色です。ここで、ノード同士の色を何度でも入れ替えられるとき、辺でつながれた隣接ノード同士が同じ色にならないような配置が可能かどうかを判定します。 たとえば、入力が次のような木だったとします。 この場合の出力は True です。色を入れ替えることで、次のようにすべての隣接ノードが異なる色になる状態を作れるからです。 解法のアプローチ この問題は、次の手順で解くことができます。 colors := 空のマップ(各色を持つノードの個数を記録) prop := 空のマップ(フラグごとのノード数を記録) dfs() 関数

問題の概要 二分木と値 k が与えられたとき、あるノードからその子孫へ向かうパスのうち、通過するノードの値の合計がちょうど k と一致するものがいくつ存在するかを求める問題です。 例えば、次のような二分木を考えてみましょう。 このとき k = 5 であれば、出力は 2 となります。条件を満たすパスは [2, 3] と [1, 4] の2つだからです。 解き方のアプローチ:累積和(prefix sum)の活用 この問題は「累積和(prefix sum)」というテクニックを使うことで、全ノードを一度だけ訪問する効率的なアルゴリズムとして解けます。考え方の手順は以下の通りです。 count:マッ

問題の概要 2次元の行列で森を表すことを考えます。各マスは次の3種類のいずれかです。 0:空き地(何もないマス) 1:木のあるマス 2:燃えている木のマス 毎日、上下左右に隣接するマス(斜め方向は含まない)の木が燃えていると、その木にも火が燃え移ります。このときすべての木が燃え尽きるまでにかかる日数を求めてください。もし全部の木を燃やすことが不可能な場合は -1 を返します。 入力例 たとえば、次のような森が与えられたとします。 121101111 この場合の出力は 4 になります。上段中央の燃えている木から火が1日ごとに周囲へ広がり、4日目についに最後の木が燃え尽きるためです。

問題の概要1から9の範囲にある数字が、固定された順序でリストとして与えられます。これらの数字の間に「+」「-」「*」「/」（/は整数除算を表す）の演算子を挿入し、さらに括弧でグループ化することで、計算結果を24にできるかどうかを判定するのがこの問題です。例えば、入力が nums = [5, 3, 6, 8, 7] の場合、(5 * 3) - 6 + (8 + 7) = 24 となるため、出力は True になります。解決のアプローチこの問題は、再帰的な分割統治法を用いて効率的に解くことができます。数列を前半と後半に分割し、それぞれの部分で作り出せるすべての値を列挙して、それらを4種類の演算子で

8パズルは、3×3の盤面に0から8までの重複しない数字が配置された古典的なスライディングパズルです。0（空白）は上下左右の隣接マスと入れ替えることができ、すべての数字を昇順に並べ替えた状態（0, 1, 2, ..., 8）を目標とします。本記事では、初期盤面からゴール状態へ到達するまでの最小手数を求めるPythonプログラムを紹介します。 問題の例 例として、次のような盤面が入力された場合を考えます。 312 475 680 この場合の出力は 4 になります。つまり、4回の入れ替え操作でゴール状態に到達できることを意味します。 解法の考え方：幅優先探索（BFS） この問題は幅優

問題概要長さ n のリストの位置 0(インデックス 0)からスタートします。各ステップでは、「右に 1 つ進む」「左に 1 つ戻る(リストの範囲外には出られない)」「その場にとどまる」のいずれかの操作を選べます。ここで、ちょうど k ステップを使って再びインデックス 0 に戻ってくる一意な移動経路(ウォーク)の総数を求めるのがこの問題です。答えが非常に大きくなる可能性があるため、10^9 + 7 で割った余りを返します。たとえば、入力が n = 7、k = 4 の場合、出力は 9 になります。条件を満たす操作列は次の 9 通りです。[右、右、左、左][右、左、右、左][待機、待機、待機、待機]

同じサイズの2つのリスト「deadlines」と「credits」があるとします。これらは講義の課題（アサインメント）を表しています。deadlines[i] は課題 i の締め切り日を、credits[i] はその課題を完了したときに得られるクレジットの量を示します。1つの課題を完了するには1日かかり、締め切り日当日またはそれ以前であれば完了できます。ただし、複数の課題を同時にこなすことはできません。ここで、いくつかの課題を選んで完了することで得られるクレジットの合計の最大値を求める必要があります。例として、deadlines = [1, 2, 2, 2]、credits = [4, 5,

問題の概要 昇順にソートされた数値リスト nums が与えられます。このリストから k 個の値を削除し、残った要素における隣接する2つの値の差の最大値ができるだけ小さくなるようにします。そして、その最小化された最大差を求めるのが目的です。 入力例 たとえば、nums = [15, 20, 30, 400, 1500]、k = 2 の場合を考えてみましょう。[400, 1500] を削除すると、残りのリストは [15, 20, 30] になります。このとき隣接する値の差は 5 と 10 であり、最大差は 10 です。これが求める出力となります。 解法の考え方 この問題は、動的計画法(DP)を用い

問題の概要ある数値 n が与えられたとき、「すべての桁が奇数である数」の中から n に最も近い値を見つけることを考えます。もし n からの距離が同じ候補が 2 つ存在する場合には、大きい方の値を返します。例えば、入力が n = 243 の場合、出力は 199 となります。243 より大きい側で最も近い全桁奇数の数は 311、小さい側は 199 であり、差はそれぞれ 68 と 44。したがって、より近い 199 が答えになります。解法の考え方この問題は、次の手順で解くことができます。まず first_even := -1 と初期化します。s := n を文字列化したもの、l := s の長さ と

問題の概要 互いにアナグラムの関係にある2つの文字列 S と T が与えられたとします。このとき、S 側で文字の入れ替え(スワップ)を行い、S を T とまったく同じ文字列にするために必要な最小のスワップ回数を求めるのがこの問題です。 たとえば、S = kolkata、T = katloka の場合、答えは 3 になります。次のような順序で入れ替えることで一致させられるからです。 [katloka(初期状態) → kotlaka → koltaka → kolkata] 解法のアプローチ この問題は、再帰とバックトラッキングを組み合わせることで解けます。各位置について「どの文字と入れ替えれば

ヒストグラムの各棒の高さを表す数値のリストが与えられます。このとき、棒の下に形成できる最大の長方形の面積を求める問題を考えてみましょう。 例えば、入力が nums = [3, 2, 5, 7] の場合を見てみます。 この場合の出力は 10 になります。高さ2の棒が幅5にわたって連続しているため、2 × 5 = 10 が最大の面積となります。 解法のアプローチ：スタックを使った効率的なアルゴリズム この問題は、単調増加スタックを利用することで O(n) の時間計算量で効率的に解けます。各棒について「その高さを維持できる最大の幅」を計算し、面積の最大値を更新していくのが基本の考え方です。 具

0と1だけで構成された2値行列（バイナリマトリクス）が与えられたとき、その中に含まれる「1」だけで構成される最大の正方形の面積を求めることを考えます。 例えば、次のような入力が与えられたとしましょう。 100001100000110111100011110001111000111100 この場合、出力は 16 となります。これは、行列の中央に存在する 4×4 の正方形（1がちょうど16個並んだ領域）が最大であるためです。 解法のアプローチ：動的計画法（DP） この問題は動的計画法を使うことで効率的に解くことができます。基本的なアイデアは、各セルに対して「そのセルを右下の角とする最大の正方形の

ここでは、2つのノードの値だけが入れ替わってしまった二分木（ほぼBST）を、正しい二分探索木（BST）に復元する方法を解説します。BSTでは中順走査（inorder traversal）を行うと値が必ず昇順に並ぶという性質があるため、この性質を利用して入れ替わったノードを検出・修正できます。例えば、次のような入力が与えられたとします。これを修正すると、出力は次のようになります。解決のための手順この問題は、以下のアルゴリズムで解決できます。変数を初期化する：prev_node := null、min_node := null、max_node := nullfound_one := False

二分木（バイナリツリー）が与えられたとき、木の中にある最長の連続パスの長さを求めることを考えます。ここでの「連続パス」とは、隣り合うノードの値が1ずつ増加、または1ずつ減少していくようなノードの並びのことです。問題の例例えば、次のような二分木が入力として与えられたとします。この場合、最も長い連続シーケンスは [2, 3, 4, 5, 6] となるため、出力は 5 になります。解き方のアプローチこの問題は、再帰的に各ノードを訪問しながら「増加パス」と「減少パス」の長さを追跡することで解けます。手順は以下の通りです。ルートがnullの場合は0を返す最大パス長を記録する変数 maxPath を0で初

問題の概要 複数の箱(ボックス)のリストがあり、各行はそれぞれの箱の幅と高さを表しているとします。ある箱は、幅と高さがどちらも相手の箱より小さい場合に限り、別の箱の中に収めることができます。この条件のもとで、1つの箱の中に最大で何個の箱を入れ子にできるかを求めるのがこの問題です。 例として、次の入力を見てみましょう。 幅高さ1212101066510 この場合の出力は 3 になります。[6, 6] の箱を [10, 10] の箱の中に収め、さらにそれを [12, 12] の箱の中に収めることができるためです。なお [5, 10] の箱は、幅は [10, 10] より小さいものの高さが等しいため