Python

この記事では、3つの整数 n、index、maxSum が与えられたとき、条件を満たす配列 nums の中で nums[index] の最大値を求める問題をPythonで解く方法を解説します。問題の条件配列 nums は以下の条件をすべて満たす必要があります。nums のサイズは n であるnums のすべての要素は正の整数であるすべての i（0 <= i < n-1）に対して |nums[i] - nums[i+1]| <= 1 が成り立つnums の全要素の合計は maxSum を超えないnums[index] を最大化する入力例と出力例たとえば、n = 6、index

配列 nums が与えられたとき、その配列を昇順または降順のどちらかの順序でソートするために必要なスワップ（要素の交換）回数を求める問題を考えてみましょう。 例えば、入力が nums = [2, 5, 6, 3, 4] の場合、出力は 2 になります。最初、nums は [2, 5, 6, 3, 4] です。まず 6 と 4 を交換すると配列は [2, 5, 4, 3, 6] になり、続いて 5 と 3 を交換すると [2, 3, 4, 5, 6] となり昇順に整列します。つまり、この配列をソートするには 2 回のスワップが必要です。 解き方のアプローチ この問題は、各要素が本来あるべき位置

問題の概要 「N桁の整数のうち、隣り合うどの2つの桁の絶対差もKと等しくなるものをすべて求める」という問題を考えます。ただし、答えとなる数には先頭のゼロを含めてはいけません（数値0自体は例外です）。 例えば、入力が N = 4、K = 7 の場合、出力は [1818, 2929, 7070, 8181, 9292] となります。1818 を確認してみると、隣接する桁同士の差は |1−8| = 7、|8−1| = 7、|1−8| = 7 となっており、条件を満たしています。一方、0707 は先頭に0が付いているため、有効な数として扱われません。 解き方のアプローチ この問題は、幅優先探索（BF

文字列 s には、括弧「(」「)」と小文字の英字が含まれているとします。この文字列から、任意の位置にある括弧「(」または「)」を最小限だけ削除し、結果として得られる括弧列を有効な状態にします。そして最終的に、有効な文字列を1つ返す必要があります。 ここで、括弧列が「有効」とみなされるのは、以下の条件のいずれかを満たす場合です。 文字列が空であるか、小文字の英字のみを含む場合 文字列が AB(A と B を連結した形)と表せる場合。ただし A と B はどちらも有効な文字列 文字列が (A) の形式で表せる場合。ただし A は有効な文字列 たとえば、入力が s = m)n(o)p の場

問題概要文字列形式で与えられた数値 s のすべての部分文字列を整数とみなし、その合計を求めます。答えは非常に大きな値になる可能性があるため、109+7 で割った余りを返します。たとえば入力が s = "268" の場合、部分文字列は "2"、"6"、"8"、"26"、"68"、"268" の6つで、合計は 2 + 6 + 8 + 26 + 68 + 268 = 378 となります。考え方：各桁の「寄与」に着目する部分文字列をすべて列挙して足し合わせる素朴な

2つの文 s と t が与えられたとき、それらが「類似」しているかどうかを判定する問題を考えてみましょう。ここで扱う文は英字のみで構成されているものとします。2つの文が類似しているとは、どちらか一方の文の中に任意の文(空文字列でも可)を挿入することで、両者が完全に等しくなる場合を指します。 例えば、s = we live at city Kolkata、t = city Kolkata という入力の場合、出力は True になります。これは、t に文 we live at を追加することで s と一致させられるためです。 解法のアプローチ この問題は、次の手順で解くことができます。 s1

はじめに 「8時15分」のような数値的な時刻を、英語では「quarter past eight(8時15分過ぎ)」や「half past nine(9時半)」といった独特のテキスト表現で表します。この記事では、時(hour)と分(minute)の2つの数値を入力として受け取り、それらを自然な英語の時刻表現に変換するPythonプログラムの作り方を解説します。 変換ルールの例 このプログラムが出力する時刻表現は、英語圏で一般的に使われる慣用表現に従います。具体的には以下のとおりです。 8:00 → 8 oclock(8時ちょうど) 8:01 → one minute past eight(8

問題概要 非負の整数からなる配列 nums が与えられたとき、その中に含まれる「素敵なペア(nice pairs)」の個数を求めます。答えが非常に大きくなる可能性があるため、10^9+7 で割った余りを返します。 インデックスのペア (i, j) が「素敵なペア」とみなされるのは、以下の条件をすべて満たす場合です。 0 <= i < j < nums のサイズ nums[i] + rev(nums[j]) が nums[j] + rev(nums[i]) と等しい 注意: rev() は整数の正の部分のみを反転します。たとえば rev(564) は 465 を返しますが、

問題の概要 文字列 s が与えられたとき、s とそのすべての接尾辞（末尾から1文字ずつ短くした部分文字列）との「類似度」の合計を求めます。ここで2つの文字列の類似度とは、両方の文字列に共通する最長の接頭辞（先頭からの一致部分）の長さのことです。 例として、入力が s = "pqpqpp" の場合を考えてみましょう。この文字列の接尾辞は次の6つです。 "pqpqpp"（元の文字列そのもの） "qpqpp" "pqpp" "qpp" "pp" "p" それ

問題の概要 2つの文字列 s と t が与えられます。これらを使って「マージ」と呼ばれる新しい文字列を、次のルールで作成します。s または t のどちらかが空になるまで、以下のいずれかの操作を選んで繰り返します。 s が空でない場合： s の先頭の1文字をマージ結果の末尾に追加し、その文字を s から取り除きます。 t が空でない場合： t の先頭の1文字をマージ結果の末尾に追加し、その文字を t から取り除きます。 このとき、作成可能なマージの中で辞書順（lexicographical order）で最も大きい文字列を求めるのが目的です。 具体例 たとえば、s = zxyxx、t =

同じサイズを持つ2つの正数配列 nums1 と nums2 があるとします。これらの配列の絶対差合計（absolute sum difference）とは、各インデックス i（0 ≤ i < n）における |nums1[i] − nums2[i]| の総和のことです。ここで、絶対差合計を最小化するために、nums1 の要素を最大1つだけ、nums1 内に存在する別の任意の要素で置き換えることができるものとします。このとき、要素を最大1つ置き換えた後の最小絶対差合計を求めてください。答えは非常に大きな値になる可能性があるため、10^9 + 7 で割った余りを返します。問題の例たとえば、入力

問題の概要配列 nums と整数 k が与えられます。部分配列の中にちょうど k 個の奇数が含まれているとき、その部分配列を「ナイスな部分配列（nice subarray）」と呼ぶことにします。このとき、ナイスな部分配列が全体で何個存在するかを求めるのが本記事のテーマです。たとえば、入力が nums = [1,1,2,1,1]、k = 3 の場合、出力は 2 になります。これは、[1,1,2,1] と [1,2,1,1] の2つの部分配列が、それぞれちょうど3つの奇数を含んでいるためです。解決のためのアプローチこの問題は、配列内の奇数が出現するインデックスをあらかじめ記録しておき、連続する k

数列 X1, X2, …, Xn が「フィボナッチ型」とみなされるのは、次の条件を満たす場合です。n >= 3 であることすべての i + 2 <= n について、Xi + Xi+1 = Xi+2 が成り立つことここで、厳密に増加する配列 A が与えられたとします。このとき、A から選び出せる最も長いフィボナッチ型の部分列の長さを求めます。条件を満たす部分列が存在しない場合は 0 を返します。たとえば、入力が A = [1,2,3,4,5,6,7,8] の場合、出力は 5 になります。これは、長さ 5 のフィボナッチ型部分列 [1,2,3,5,8] が存在するためです。解法の考え方

問題の概要 あらかじめソートされたサイズnの配列numsが与えられているとします。この配列に対して、次のクエリをn回実行することを考えます。 配列nums内のすべての要素とkとのXORが最大化されるような、非負の値k（k < 2^m）を求めます。このkがi番目のクエリに対する答えになります。 現在の配列numsから末尾の要素を1つ削除します。 そして、i番目のクエリへの答えがanswer[i]となるような配列answerを求めるのが目的です。 入力例と出力例 たとえば、入力がnums = [0,1,1,3]、m = 2の場合、出力は[0,3,2,3]になります。その理由は以下の通り

本記事では、Pythonを使って「所持しているコインで最大いくつのアイスクリームを買えるか」を求めるアルゴリズムを解説します。問題の概要n個の要素を持つ配列 costs が与えられます。costs[i] は i 番目のアイスクリームの価格（コイン単位）を表します。最初に c 枚のコインを持っており、できるだけ多くのアイスクリームを購入したいと考えます。このとき、c 枚のコインで買えるアイスクリームの最大数を求めるのが目的です。たとえば、入力が costs = [3,1,4,5,2]、c = 10 の場合、出力は 4 になります。これは、インデックス 0、1、2、4 のアイスクリームを合計 3

問題の概要配列 nums と整数 k が与えられます。1回の操作ごとに、nums 内の任意のインデックスを1つ選び、その位置の要素の値を1だけ増やすことができます。操作は最大 k 回まで行えるとき、最終的にある1つの要素が持ち得る最大の出現頻度（同じ値の個数）を求めてください。たとえば、入力が nums = [8,3,6]、k = 9 の場合、出力は 3 になります。要素 3 を5回、要素 6 を2回増やすことで配列を [8,8,8] にでき、合計7回の操作で頻度3を達成できるためです。アプローチ：ソート＋スライディングウィンドウこの問題は、配列をあらかじめソートしておき、スライディングウィン

問題の概要英字の母音（a、e、i、o、u）のみで構成された文字列 s が与えられたとします。この中から「美しい部分文字列」の条件を満たす部分文字列のうち、最も長いものの長さを求めます。該当する部分文字列が存在しない場合は 0 を返します。ここで「美しい文字列」とは、以下の2つの条件を満たす文字列のことです。5種類の母音（a、e、i、o、u）がそれぞれ少なくとも1回以上出現すること文字がアルファベット順（a → e → i → o → u）に並んでいること例えば、入力が s = aaioaaaaeiiouuooaauu の場合、出力は 10 になります。これは部分文字列 aaaaeiiouu が

問題の概要 配列 nums と整数 goal が与えられます。ここから部分列(元の順序を保ちながら任意の要素を選んだもの)を1つ選び、その要素の合計 s が goal にできるだけ近づくようにします。言い換えれば、絶対差 |s − goal| を最小化することが目的です。 例として、nums = [8, -8, 16, -1]、goal = -3 が入力された場合を考えてみましょう。このとき出力は 2 になります。部分列 [8, -8, -1] を選ぶと合計は -1 となり、|-1 − (-3)| = 2 が達成可能な最小値だからです。 解法の考え方 すべての部分列を素朴に列挙すると、組み合

問題の概要 2つの文字列 s と t があるとします。s の中の2文字の位置をちょうどK回入れ替えることで s を t と同一の文字列にできるとき、この2つの文字列はK類似（K-similar）であると定義されます。 ここでは、互いにアナグラムの関係にある2つの文字列 s と t が与えられ、s と t がK類似となる最小のKを求めることを目標とします。 たとえば、入力が s = abc、t = bac の場合、出力は 1 になります。「a」と「b」を1回入れ替えるだけで abc → bac と変換できるためです。 解法の考え方：幅優先探索（BFS） この問題は、各文字列の状態をノード、1回

本記事では、n個の座席の予約状態を管理するシステムをPythonで設計・実装する方法を解説します。座席には1からnまでの番号が振られており、これらを効率的に管理する「SeatReserveManager」クラスを作成していきます。 実装すべき機能の概要 SeatReserveManagerクラスには、以下の3つの機能を実装します。 コンストラクタ（__init__）：引数としてnを受け取り、1からnまでの番号が付いたn個の座席を管理するオブジェクトを初期化します。初期状態では、すべての座席が予約可能です。 reserve()：現時点で予約されていない座席の中から最も番号の小さい座席を取得し