Python

問題の概要クエリのリスト Q が与えられ、各クエリ Q[i] は [a_i, b_i, d_i] という3つの値から構成されているとします。初期位置は (0, 0) であり、1ステップごとに、現在位置 (x1, y1) から2点間のユークリッド距離が a 以上 b 以下となる任意の点 (x2, y2) へ移動できます。各クエリに対して、(0, 0) から (d_i, 0) へ到達するために必要な最小ステップ数を求めるのがこの問題の目的です。たとえば、入力が Q = [(2,3,1), (1,2,0), (3,4,11)] の場合、出力は [2, 0, 3] となります。その理由は以下の通りです

少なくとも1つの要素の値が 1 である数値リスト nums が与えられたとします。このとき、リスト内のすべての 1 が連続して並んでいるかどうかを判定する問題を考えてみましょう。 たとえば、入力が nums = [8, 2, 1, 1, 1, 3, 5] の場合、1 は途中で途切れることなく連続して出現しているため、出力は True になります。 一方、入力が [8, 2, 1, 3, 1, 5] のような場合は、1 が離れて出現しているため、出力は False となります。 アルゴリズムの考え方 この問題は、状態を表すフラグ変数を1つ用意することで効率的に解けます。手順は以下の通りです。

問題概要 数値のリスト nums が与えられたとき、その要素 x のうち「x + 1」という値も同じ配列内に存在するものの個数を求める問題です。 例えば、nums = [4, 2, 3, 3, 7, 9] の場合、出力は 3 になります。その理由は以下の通りです。 2 + 1 = 3 が配列内に存在する 3 + 1 = 4 が配列内に存在する もう一つの 3 も同様に条件を満たす これらを合わせると、条件を満たす要素は合計 3 個となります。 解法のアプローチ この問題は、各要素の出現回数を記録しておき、隣接する値(i + 1)が存在するかどうかを効率的に確認することで解けます。具体的な

サイズが n + 1 の整数リスト nums があり、その要素はすべて範囲 1, 2, ..., n の中から選ばれているとします。このとき、鳩の巣原理（Pigeonhole Principle）より、リスト内には必ず少なくとも1つの重複した値が存在します。この重複している要素を見つけるのが本記事の目的です。さらに、ここでは計算量 O(n)・追加メモリ O(1)（定数空間）という制約のもとで解くことを目標とします。問題の例たとえば、入力が次のような場合を考えてみましょう。nums = [2, 1, 4, 3, 5, 4]この場合、重複している値は 4 なので、出力は 4 となります。解法の考え

リストpointsに格納された一連のデカルト座標点（直交座標点）を考えます。これらの点を、それぞれの極角（偏角）に基づいて並べ替える必要があります。極角は0から2πの範囲で表されます。もし複数の点が同じ極角を持つ場合は、その点の原点からの距離に基づいて並べ替えます。例えば、入力が points = [(1,1), (1,-2),(-2,2),(5,4),(4,5),(2,3),(-3,4)] の場合、出力は [(5, 4), (1, 1), (4, 5), (2, 3), (-3, 4), (-2, 2), (1, -2)] となります。解決のための手順この問題を解くために、以下の手順に従いま

問題概要2つのリスト nums1 と nums2 が与えられ、それぞれの要素は 1 以上 6 以下の整数です。ここで、「どちらかのリストから1つの数を選び、その値を 1〜6 の範囲内の任意の数に更新する」という操作を考えます。この操作を繰り返して2つの配列の合計値を等しくするとき、必要な最小の操作回数を求めてください。どうしても等しくできない場合は -1 を返します。例えば、nums1 = [1, 4]、nums2 = [5, 4, 4] が入力された場合、答えは 2 になります。まず nums1 の 1 を 6 に変更すれば nums1 の合計は 10 になり、次に nums2 の 4 のう

問題概要数値のリスト nums が与えられたとき、i < j を満たし、かつ nums[i] と nums[j] が等しいようなインデックスのペア (i, j) の個数を求めることを考えます。たとえば、入力が nums = [5, 4, 5, 4, 4] の場合、出力は 4 になります。これは、(0, 2)、(1, 3)、(1, 4)、(3, 4) の4つのインデックスペアが条件を満たすためです。解法のアプローチこの問題は、各値の出現回数を集計してから組み合わせの数を足し合わせることで、効率的に解くことができます。手順は以下の通りです。Python標準ライブラリの Counter を使い

問題概要 整数 n が与えられたとき、「0」と「9」の2種類の数字だけで構成され、かつ n の倍数となる最小の正整数 x を求めることを考えます。 例えば、入力が n = 26 の場合、出力は 90090 となります。 解法のアプローチ この問題は、次の手順で解くことができます。 m を 9 に初期化する x を 1 に初期化する m が n で割り切れない間、以下を繰り返す x を 1 増やす x の2進数表現に含まれるすべての「1」を「9」に置き換えた数を m とする m を整数として返す この方法のポイントは、0と9のみで構成される数は、2進数の「0」と「1」で構成される数と同

数値のリスト nums が与えられたとき、「その値自身と出現回数（頻度）が一致している要素」がリスト内に存在するかどうかを判定する問題を考えます。 たとえば、入力が nums = [2,5,7,5,3,5,3,5,9,9,5] の場合、値 5 がちょうど5回出現しているため、出力は True になります。 解決のアプローチ この問題は、次の手順で解くことができます。 nums_c := nums 内に存在する各要素の出現頻度を格納したリストを作成する nums_c 内の各値 i とその頻度 j について以下を繰り返す i と j が等しい場合は True を返す 該当する要素が見つか

リスト nums に含まれるすべての要素が偶数回出現しているかどうかを判定したいケースはよくあります。本記事では、追加のメモリをほとんど使わない「定数空間(O(1))」でこの問題を解く方法を紹介します。たとえば、入力が nums = [8, 9, 9, 8, 5, 5] の場合、8・9・5 はそれぞれ2回ずつ出現しているため、出力は True になります。解法のアプローチこの問題は、次の手順で解決できます。まず、リスト nums の長さが奇数である場合は、少なくとも1つの要素が奇数回出現することになるため、即座に False を返します。リスト nums をソートします。これにより、同じ値の要

ローカルピークとは？ 長さ2以上の数値リスト nums が与えられたとき、リスト内に存在するすべての「ピーク（山）」のインデックスを求める問題を考えます。 あるインデックス i がピークであるとは、以下のいずれかの条件を満たす場合を指します。 i = 0 の場合：nums[i] > nums[i + 1] i = n - 1 の場合：nums[i] > nums[i - 1] 上記以外の場合：nums[i - 1] < nums[i] > nums[i + 1] つまり、リストの端にある要素は隣接する1つの要素より大きければピークとみなされ、それ以外の要素は両側の隣

フィボナッチ数とは ある数値 n が与えられたとき、その数がフィボナッチ数列に含まれているかどうかを判定します。フィボナッチ数列は、f(0) = 0、f(1) = 1 を初期値とし、i ≥ 2 の各項について f(i) = f(i-1) + f(i-2) という漸化式で定義される数列です。 具体的には、数列は 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... のように続きます。たとえば入力が n = 13 の場合、13 はフィボナッチ数列に含まれるため、出力は True になります。 解法のアプローチ:黄金比を利用した判定 この問題は、黄金比(φ ≈ 1.618...

数値のリスト rooms と目標値 t が与えられたとします。このとき、rooms の中で t 以上となる最初の値を見つける必要があります。該当する値が存在しない場合は -1 を返します。 例えば、入力が rooms = [20, 15, 35, 55, 30]、t = 30 の場合、出力は 35 になります。これは、リストを先頭から順に確認したときに、初めて 30 以上となる値が 35 だからです。それ以前の要素(20 や 15)は目標値 30 を満たしていません。 解決のアプローチ この問題は、以下の手順で解くことができます。 rooms 内の各要素 room を先頭から順に調べる r

問題の概要すべての要素が重複なく、昇順にソートされたリスト nums が与えられます。この中から、nums[i] = i(要素の値とインデックスが一致する)を満たす最小のインデックス i を見つける必要があります。条件を満たすインデックスが存在しない場合は -1 を返してください。さらに、この問題は O(log n) の時間計算量で解くことが求められています。たとえば、入力が nums = [-4, -1, 2, 3, 8] の場合、出力は 2 となります。nums[2] = 2 と nums[3] = 3 の両方が条件を満たしていますが、より小さい方の「2」が答えになるためです。解法の考え方

小文字のみで構成された文字列 s が与えられます。ここで求めたいのは、文字列内の別の場所に、その部分文字列のアナグラム（文字を並べ替えたもの）が必ず存在するような部分文字列をすべて見つけ、辞書順（辞書式順序）にソートしたリストとして返すことです。 たとえば、入力が s = abcba の場合、出力は以下のようになります。 [a, a, ab, abc, abcb, b, b, ba, bc, bcba, cb, cba] これらの各部分文字列について、元の文字列内の異なる位置に対応するアナグラムが実際に存在することを確認できます。なお、同じ文字（たとえば a）が複数回現れるのは、出現位置ごとに

問題の概要 2つの整数 n と k が与えられたとき、「n を k 個の素数の和として表すことができるか」を判定するプログラムを考えます。 例えば、入力が n = 30、k = 3 の場合、出力は True になります。これは、30 が 2 + 11 + 17 という3つの素数の和で表せるためです。 解法のアルゴリズム この問題は、次の手順に従って判定できます。 n < k × 2 の場合:False を返します。最小の素数は 2 なので、k 個の素数の和は必ず 2k 以上になります。したがって、n が 2k 未満であれば表現は不可能です。 k > 2 の場合:True を返

Pythonでは、mathモジュールのgcd()関数を活用することで、リスト内のすべての整数に共通する最大公約数（GCD：Greatest Common Divisor）を簡単に求めることができます。例えば、リスト nums = [15, 81, 78] が与えられた場合、15・81・78 のすべてを割り切れる最大の正の整数は 3 であるため、出力結果は 3 になります。解法のアプローチこの問題は、以下の手順で解決できます。リストの要素数が1つだけの場合は、その要素をそのまま返します。まず、最初の2つの要素 nums[0] と nums[1] の最大公約数を計算し、変数 div に格納します。

リスト nums が与えられたとき、「あるインデックス i の左側にある要素の合計」と「右側にある要素の合計」が等しくなるような、最小のインデックス i を求めることを考えます。該当するインデックスが存在しない場合は -1 を返します。 例えば、入力が nums = [8,2,3,6,5,2,5,9,1,2] の場合、出力は 4 となります。これは、インデックス 4 の左側の要素 [8,2,3,6] の合計が 19、右側の要素 [2,5,9,1,2] の合計も 19 となり、両者が一致するためです。 解法のアプローチ この問題を効率的に解くには、リスト全体の合計をあらかじめ計算しておき、左から

2つの文字列 s1 と s2 が与えられたとき、両方の文字列にとって「特殊部分列」となる最長の文字列 s3 の長さを求めることを考えます。ある文字列 x が別の文字列 y の特殊部分列であるとは、y から 0 個以上の文字を削除することで x が生成できることを意味します。これは、いわゆる「部分列(サブシーケンス)」と呼ばれる概念で、文字同士の順序関係さえ保たれていればよく、連続している必要はありません。例として、s1 = pineapple、s2 = people が入力された場合を考えてみましょう。この場合の出力は 5 になります。長さ 5 の特殊部分列 peple が存在するためです。こ

はじめに連結リスト（Linked List）に複数の要素が格納されており、指定した位置 pos の直前に新しい値 val を挿入したいケースは、データ構造の学習において非常に重要なトピックです。本記事では、Python を使って単方向連結リストの指定インデックスの直前に要素を挿入するプログラムを分かりやすく解説します。例えば、nums = [1,5,3,6,8]、pos = 3、val = 7 という入力が与えられた場合、出力は [1,5,3,7,6,8] となります。つまり、インデックス3の位置にある「6」の直前に新しい値「7」が挿入されることになります。アルゴリズムの手順この問題は、以下の