Python

問題の概要 2つの整数 A と B が与えられたとき、「A で割り切れ、かつ各桁の数字の合計が B と等しい」という条件を満たす最小の正の整数 M を求めます。そのような数が存在しない場合は -1 を返します。 例えば、入力が A = 50、B = 2 の場合、出力は 200 となります。200 は 50 で割り切れ、桁の合計も 2 + 0 + 0 = 2 となり、両方の条件を満たす最小の数だからです。 解法のアプローチ：幅優先探索（BFS） この問題は幅優先探索（BFS）を用いることで効率的に解けます。BFS は桁数の少ない数から順に探索を進めるため、最初に見つかった解が必ず最小値になりま

問題概要1からNまでの整数が円環状に並んだリングがあるとします。さらに、2つの整数 A と B が与えられます。ここで、リング上の任意の位置(これを X とします)に立ち、X から A までの距離と X から B までの距離の合計(Z = X から A への距離 + X から B への距離)を考えます。この合計 Z を最小化するような位置 X を選び、その値を返すのが目的です。ただし、X は A および B と同じ位置であってはならないという制約がある点に注意してください。例えば、入力が N = 30、A = 10、B = 20 の場合、出力は 10 になります。これは、X = 15 を選ぶと

統計学では、複数のデータ系列をひとつにまとめたときの平均や分散を求めたい場面がよくあります。本記事では、それぞれ異なるサイズを持つ2つの系列 A1 と A2 を結合した系列について、その結合平均（Combined Mean）と結合分散（Combined Variance）をPythonで計算する方法を解説します。問題の概要サイズ n の系列 A1 と、サイズ m の系列 A2 が与えられたとき、これらを結合した系列全体の平均と分散を求めることを考えます。例えば、次のような入力があったとします。A1 = [24, 46, 35, 79, 13, 77, 35]（要素数：7）A2 = [66, 6

n個の整数からなる2つの配列 A と B が与えられ、i番目の要素が d * A[i] + B[i] で表される配列 C を考えます。ここで d は任意の実数です。本記事では、配列Cに含まれるゼロ（0）の個数が最大になるような d の値を求め、あわせてそのゼロの個数を返す方法を解説します。 たとえば、入力が A = [15, 40, 45]、B = [4, 5, 6] の場合、出力は d = -0.266666、ゼロの個数は 1 となります。 解法のポイント この問題の鍵は、C[i] = d * A[i] + B[i] が0になる条件を整理することです。 C[i] = 0 となるのは d

問題の概要 m × m の正方行列が与えられたとき、すべての行に共通して現れる重複しない要素をすべて抽出することを考えます。 たとえば、次のような入力が与えられたとしましょう。 13215417 1532436 15215412 1526432 21942215 この場合、すべての行に共通して含まれる要素は 2、4、15 の3つであるため、出力は [2, 4, 15] となります。 解決のためのアプローチ この問題は、マージソートの「マージ処理」に似た発想で効率的に解くことができます。ポイントは、各行をあらかじめソートしておき、ポインタを進めながら共通要素を探すことです。具体的な手順

n個の数値からなる配列があるとします。nは最大でも32,000であり、配列には重複した要素が含まれている可能性がありますが、nの具体的な値は分かりません。ここで、使用できるメモリがわずか4キロバイトしかないという制約のもと、配列内のすべての重複をどのように表示すればよいでしょうか?例えば、入力が [2, 6, 2, 11, 13, 11] の場合、2と11がそれぞれ複数回出現しているため、出力は [2, 11] となります。なぜビット配列なのか通常、重複検出にはハッシュセットなどを使用しますが、32,000個の整数をそのまま格納すると必要なメモリが制限を超えてしまいます。そこで各数値を「1ビッ

問題の概要数値 l と、単調増加する数列 f(m) が与えられます。この数列は次の式で定義されます。f(m) = am + bm・[log₂(m)] + cm³ここで、a = 1, 2, 3, …、b = 1, 2, 3, …、c = 0, 1, 2, 3, … です。[log₂(m)] の意味[log₂(m)] は底が2の対数を計算し、小数点以下を切り捨てた値を表します。具体的には次のようになります。m = 1 のとき → 0m = 2〜3 のとき → 1m = 4〜7 のとき → 2m = 8〜15 のとき → 3（以降も同様）求めるべきものf(m) = l を満たす m の値を見つけるこ

初項 A と公差 D を持つ等差数列（AP）と、素数 P が与えられたとき、その等差数列の中で初めて素数 P の倍数になる項の位置（何番目の項か）を求める問題を考えてみましょう。問題の例たとえば、A = 3、D = 4、P = 5 という入力の場合、答えは 3 になります。これは、この等差数列の第4項（インデックス3）が素数 5 の倍数であるためです。第1項 = 3第2項 = 3 + 4 = 7第3項 = 3 + 2×4 = 11第4項 = 3 + 3×4 = 15（5 の倍数）解法のアプローチk 番目の項は A + k×D で表されます。これが P の倍数になる条件は、次の合同式で表せます。

問題の概要 ある整数 N が与えられたとき、N の約数の中から次の 2 つの条件を同時に満たす 4 つの約数を選び、その積を求めることを考えます。 選んだ 4 つの約数の合計が N と等しいこと その 4 つの約数の積が最大になること なお、積を最大化するうえで、4 つの約数がすべて同じ値であっても構いません。むしろ一般に、合計が固定されたときは各数ができるだけ均等に近いほど積は大きくなります。 たとえば入力が N = 60 の場合、出力は 50625 です。60 の約数は 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 ですが、この中から 15 を 4

問題の概要ここでは、1からNまでの範囲に属する相異なる整数で構成された配列を扱います。配列のサイズは N-4 であり、要素の重複は一切ありません。つまり、1からNまでのうち4つの数が配列から抜け落ちていることになります。この記事では、その4つの欠落数を昇順で特定する方法を解説します。例として、入力が A = [2, 8, 4, 13, 6, 11, 9, 5, 10] の場合、出力は [1, 3, 7, 12] となります。アルゴリズムのポイントこの問題は、追加のメモリをほとんど使わずに解決できます。鍵となるのは「符号反転」のテクニックです。配列内の値 v に対応する位置(インデックス v-1

この記事では、n個の座標点が与えられたときに、その中から辺がX軸およびY軸に平行な正方形を形成できる4つの点を見つける方法を解説します。条件を満たす正方形が存在しない場合は「不可能」を返します。また、複数の正方形が構成できる場合は、面積が最大になるものを選択します。問題の例例として、n = 6、points = [(2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)] が入力された場合を考えてみましょう。このとき出力されるのは「3」で、正方形を構成する4点は (2, 2)、(5, 2)、(2, 5)、(5, 5) となります。解法のアプローチこの問題を解

ある無向グラフが与えられたとき、そのグラフの中に指定したサイズ l の独立集合(Independent Set)が含まれているかどうかを判定します。条件を満たす独立集合が存在すれば「Yes」を、存在しなければ「No」を出力します。 独立集合とは? グラフ理論において独立集合とは、「互いに直接つながっていない(隣接関係にない)頂点だけで構成される集合」を指します。つまり、集合の中から任意の2つの頂点を選んだとき、その間に辺(エッジ)が存在してはいけません。 例として、L = 4 の場合を考えてみましょう。 このグラフの場合、出力は「Yes」となります。 解決のためのアプローチ この問題はバック

問題の概要二分木が与えられたとき、指定された垂直レベル（vertical level）に属するノードの値が昇順にソートされているかどうかを判定する問題です。垂直レベルとは、木を横から見たときに同じ縦位置に並ぶノードのグループを指し、ルートのレベルを 0 とすると、左へ移動するごとに -1、右へ移動するごとに +1 となります。なお、2つのノードが画面上で重なって見える場合でも、それぞれが属するレベル内での並び順がソートされていればよいものとします。例として level = -1 を指定した場合、そのレベルに含まれる要素は「3, 7」であり、昇順に並んでいるため、出力は True になります。解

問題の概要コストの範囲（lowCost〜upCost）と数量の範囲（lowQuant〜upQuant）が与えられたとき、r ＝ コスト ÷ 数量 となる指定の比率 r を見つけられるかどうかを判定する問題です。ここで、コストは lowCost ≤ cost ≤ upCost の範囲内、数量は lowQuant ≤ quantity ≤ upQuant の範囲内に収まっている必要があります。例えば、lowCost = 2、upCost = 10、lowQuant = 3、upQuant = 9、r = 3 という入力の場合、出力は True になります。なぜなら、コスト = r × 数量 = 3

3種類のカップが配列 p に、ソーサーが配列 q に入っており、利用できる棚の数 m が与えられているとします。このとき、カップとソーサーを「きれいに」配置できるかどうかを判定するのが本記事のテーマです。 「きれいな配置」となるための条件 カップとソーサーの配置が整然としていると言えるのは、次の3つの条件をすべて満たす場合です。 どの棚にも、カップとソーサーを混在させて置くことはできない 1つの棚に置けるカップは最大5個まで 1つの棚に置けるソーサーは最大10枚まで 入出力の例 たとえば、p = [4, 3, 7]、q = [5, 9, 10]、m = 11 という入力の場合、出力は

グラフと始点となる頂点、そして数値 k が与えられたとします。ここで k は「始点から目的地までの経路の長さ」を表します。このとき、始点から出発し、任意の頂点（目的地）で終わる、閉路（サイクル）を含まない単純パスが存在するかどうかを判定するのが本記事の目的です。問題の概要以下のような重み付き無向グラフを考えてみましょう。例として、始点 = 0、k = 64 という入力が与えられた場合を考えます。この場合の出力は True になります。なぜなら、「0 → 7 → 1 → 2 → 8 → 6 → 5 → 3 → 4」という単純パスが存在し、その総距離は 68 となり、64 を超えているためです。解

問題概要同じ長さを持つ2つの文字列S1とS2が与えられたとき、S1[0…i]とS2[i+1…n-1]を連結した結果が回文になるようなインデックスiを見つけます。そのようなインデックスが存在しない場合は、-1を返します。例えば、入力がS1 = pqrsu、S2 = wxyqpである場合を考えてみましょう。このとき出力は1になります。なぜなら、S1[0..1] = pq、S2[2..n-1] = ypqであり、これらを連結したpqyqpは回文になるためです。解法のアプローチこの問題を解くためには、以下の手順に従います。nにstr1のサイズ（長さ）を代入します空文字列strを用意しますiを0からnま

問題の概要0と1のみで構成されるバイナリ配列が与えられたとします。この配列の中から、ある1つの0を1に置き換えたときに、連続する1の並びが最も長くなる位置（インデックス）を見つけるのが本記事の課題です。例えば、入力が [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1] の場合、答えは 10 になります。インデックス10の0を1に置き換えると、配列は [1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1] となり、末尾に7個連続した1が並びます。アルゴリズムの考え方この問題は、配列を一度だけ走査（線形時間 O(n)）することで解くことができます

問題の概要 エンコードされた文字列では、部分文字列の繰り返しが「部分文字列＋出現回数」の形式で表現されます。たとえば、文字列が pq2rs2 で k=5 の場合、復号化後の文字列は pqpqrsrs となり、5番目の文字は r です。 ここで注意したいのは、出現回数が2桁以上になるケースも存在するという点です。たとえば a12b のような入力では、「a」が12回繰り返されることを正しく読み取れる必要があります。 具体例 入力として string = pq4r2ts3、k = 11 が与えられた場合を考えてみましょう。復号化後の文字列は pqpqpqpqrrtststs となるため、11番目の

問題の概要二分木が与えられたとき、左の部分木と右の部分木が完全に一致している最大の部分木を見つけることを考えます。望ましい計算量は O(n) です。例えば、次のような二分木が入力として与えられた場合を考えてみましょう。この場合、出力は次のようになります。解法のアプローチこの問題を解くためには、木をボトムアップ（下から上へ）に走査し、各ノードについて「そのノードを根とする部分木の構造を表す文字列（エンコード）」を作成します。そして、左部分木のエンコードと右部分木のエンコードが一致していれば、そのノードは「左右が同一の部分木」の根であると判断できます。具体的な手順は以下の通りです。solve()