Python

この記事では、「ロシア農民乗算法（Russian Peasant Multiplication）」の考え方を応用して、複素数のべき乗を効率よく計算するPythonプログラムを解説します。 問題設定は次のとおりです。4つの整数 p、q、r、k が与えられたとき、複素数 (p + qi) の r 乗を求めます。結果は a + bi の形で表せるので、a mod k と b mod k のペアを答えとして返します。 たとえば p = 3、q = 0、r = 8、k = 10000 が入力された場合を考えてみましょう。q = 0 なので計算は単純な 3 の 8 乗、つまり 6561 になります。したが

ある道に n 個のブロックが並んでおり、作業員がそのブロックに色付きタイルを貼っていく場面を考えてみましょう。作業員は「番号が 4 または 2 で割り切れるブロック（ただし 42 を除く）」にだけ色付きタイルを貼るというルールに従います。このとき、最初に k 枚の色付きタイルを持っている場合、何番目までのブロックをカバーできるかを求めるのがこの問題です。 例えば、入力が k = 16 の場合、出力は 32 になります。これは、偶数番号のブロック 2, 4, 6, …, 32 の計 16 個にタイルを貼ると、ちょうど 16 枚を使い切るためです。 解き方のアプローチ この問題は、42 というスキ

問題の概要 すべての要素が 0 で初期化された n × m の行列があるとします。ここに、「行と列の位置」のペアを格納したリストが与えられます。リスト内の各要素 i について、行番号と列番号がその要素の行の値・列の値より小さいすべてのセルの値が 1 ずつ加算されます。すべてのリスト要素を処理し終えた後、行列内で最大値を含むセルの個数を求める必要があります（行・列のインデックスは 0 から始まります）。 たとえば、入力が input_list = [[3, 5], [4, 6], [5, 3]] の場合、出力は 9 になります。ここでは 5 × 6 の行列を例に、処理の流れを確認してみましょう。

ここでは、n 個の頂点、n 本の反転軸(対称軸)、n 個の回転点を持つ多角形を考えます。反転軸と回転点については、以下の性質が成り立ちます。n が奇数の場合、各反転軸は1つの頂点と、その反対側の辺の中点を通ります。n が偶数の場合、半分の軸は向かい合う頂点同士を通り、残りの半分は向かい合う辺同士の中点を通ります。隣り合う2つの軸がなす角度は 360/2n 度です。問題の概要この多角形に対して操作を行います。操作には n 種類の回転器があり、k-rotator は軸 k を基準にして多角形を時計回りに (360 × k)/n 度回転させます。入力として、複数の整数ペアを含むリスト input_l

問題の概要n個のボールがあり、初期状態では「1, 2, 3, ..., n」の順に並んでいるとします。まずボール全体を反転して「n, n-1, ..., 2, 1」の順序にします。続いて、開始位置を1つ右にずらしながら再度反転を行い、この操作を合計n回繰り返します。毎回、反転の開始位置は前回より1つ右へ移動していきます。この一連の反転操作が完了した後、最初に「index」番目の位置にあったボールが最終的にどこへ移動するかを求めるのが、この記事で扱う問題です。具体例たとえば、balls = 5、index = 2 が入力された場合、出力は 4 になります。ボールの初期状態は次のとおりです。1,

整数 n が与えられたとします。[1, 2, ..., n] のような n 個の異なる値があるとき、これらの値を使って構成できるBST（二分探索木）の総数を数える必要があります。答えが非常に大きくなる可能性があるため、結果は 10^9+7 で割った余りとして返します。 たとえば、入力が n = 3 の場合、出力は 14 になります。 解法のアプローチ この問題は、動的計画法（DP）を使って効率的に解くことができます。ある値を根に選ぶと、それより小さい値で作られる左部分木と、大きい値で作られる右部分木に分割できるため、小さな部分問題の答えを組み合わせることで全体の答えが求まります。 具体的には

問題の概要 関数 f(x) を考えます。f(x) は、次の条件をすべて満たすペア (p, q) の個数を返します。 1 < p ≤ q ≤ x p と q は互いに素(最大公約数が 1) p × q = x ここで、正の整数 n が与えられたとき、x を 1 から n まで動かした場合の f(x) の総和を求めるのがこの問題の目的です。 入力例と出力例 たとえば入力が 12 の場合、出力は 3 になります。x が 1〜12 の範囲で条件を満たすのは次の 3 つだけだからです。 x = 6 のとき:有効なペアは (2, 3) のみ → f(6) = 1 x = 10 のとき:有効な

ある整数 n と個数 k が与えられたとき、「n を k 個の素数の合計として表すことができるかどうか」を判定する問題を考えてみましょう。例えば、入力が n = 30、k = 3 の場合、30 は「2 + 11 + 17」という3つの素数の合計で表せるため、出力は True になります。解法のアプローチこの問題を効率的に解くために、以下の手順に従います。n < 2×k の場合False を返す（最小の素数は2なので、k個の素数の合計の最小値は 2×k になるため）k > 2 の場合True を返す（任意の n ≥ 2k は k 個の素数の合計として必ず表現できることが知られているた

問題の概要 ここでは、「Ajob言語」という奇妙な言語を考えます。この言語には無限個の文字が存在します。私たちはこの言語のn個の単語を知っており、1番目の単語は1文字、2番目の単語は2文字、3番目の単語は3文字……というように、i番目の単語の長さはちょうどi文字になっています。さらに、各単語を構成する文字はすべて互いに異なります。 このn個の単語の中から任意の1つを選び、その部分列(元の並びの一部を抜き出した列)を作ることを考えます。ただし、部分列の長さは元の単語の長さよりkだけ短くなければなりません。つまり、選んだ単語の長さをLとすると、部分列の長さは(L − k)です。長さがk未満の単語

ある数値 A が与えられたとします。このAを n回連結 して大きな数Xを生成し、そのXを m で割った余り（モジュラス）を求めるのが今回の課題です。 例えば、入力が A = 15、n = 3、m = 8 の場合を考えてみましょう。このとき生成される数値Xは「151515」となり、151515 mod 8 = 3 であるため、出力は 3 になります。 解法のアプローチ 連結後の数値は桁数が膨大になる可能性があるため、実際に文字列として連結してから計算するのは非効率です。そこで、数学的な性質を利用して直接剰余を計算します。手順は以下の通りです。 Aが0の場合は、0を返す an := A c :=

サイズ n の数列 nums が与えられます。この中から、任意のペア (p, q) がすべて「良いペア(nice pair)」となるような nums の部分列の最大サイズを求めることを考えます。あるペアが「良いペア」であるとは、次の条件のうち少なくとも1つを満たす場合を指します。p が持つ相異なる素因数の個数の偶奇が、q のそれと一致する。たとえば 18 の相異なる素因数は 2 と 3 の2つです。p の正の約数の総和の偶奇が、q のそれと一致する。たとえば、入力が nums = [2,3,6,8] のとき、出力は 3 になります。解き方の手順この問題を解くには、次の手順に従います。n :=

2次元平面上に置かれた2つの長方形が覆う総面積を求めたい場面を考えてみましょう。各長方形は、左下の頂点と右上の頂点の座標によって定義されます。1つ目の長方形の左下・右上の座標をそれぞれ (A, B)、(C, D)、2つ目の長方形のそれらを (E, F)、(G, H) とします。解き方のアプローチこの問題は、以下の手順で解くことができます。まず、それぞれの長方形の幅と高さを求めます。width_1 := |C − A|、height_1 := |D − B|width_2 := |G − E|、height_2 := |H − F|2つの長方形の面積を合計します。area := width_1

はじめにプログラミングでは、nCr(組み合わせの数)を何度も計算する必要がある場面がよくあります。実は、すでに計算した小さな値を保存しておけば、より大きな値を非常に効率的に求めることができます。具体的には、整数 n が与えられたとき、nC0 から nCn までのすべての値をリストとして求めます。ただし、答えが大きくなりすぎる場合は、10^9 で割った余りを返します。例えば、入力が n = 6 の場合、出力は [1, 6, 15, 20, 15, 6, 1] となります。アルゴリズムの考え方この問題を解く鍵となるのは、次の漸化式です。nCr = nC(r−1) × (n − r + 1) / r

問題概要額面が1ルピー・2ルピー・5ルピー・10ルピーのコインが、それぞれ限られた枚数だけ手元にあるとします。これらのコインを組み合わせて、合計がちょうどnルピーになる方法が何通りあるかを求めるのがこの問題です。サイズ4の配列countが与えられ、count[0]には1ルピーコインの枚数、count[1]には2ルピーコインの枚数、以降も同様に各額面の枚数が格納されています。たとえば、入力が n = 25、count = [7, 3, 2, 2] の場合、答えは9通りになります。解き方のアルゴリズムこの問題は動的計画法(DP)を応用して解けます。各額面のコインを1種類ずつ順に追加していき、その時

文字列 s が与えられたとき、その文字を使って作れる「すべての組み合わせ」を求めます。同じ文字の集合からなる文字列が複数存在する場合は、辞書順で最小のものだけを出力します。なお、s に含まれる文字はすべて一意（重複なし）であるという制約があります。 たとえば、入力が s = pqr の場合、出力は [r, qr, q, pr, pqr, pq, p] のようになります。 解き方の手順 この問題は、文字列を末尾から先頭へ向かって走査し、それまでに生成した部分文字列のそれぞれに現在の文字を連結していくことで解決できます。具体的には次のステップに従います。 st_arr := 結果を格納する新しい

2つのリスト nums1 と nums2 があるとします。ここでの制約は、マージを行う際に各リスト内の要素の相対的な順序が変わらないことです。例えば、要素が [1,2,3] と [4,5,6] の場合、[1,4,2,3,5,6] や [1,2,3,4,5,6] などが有効なマージ結果となります。他にも有効なマージ順序は存在します。リストのサイズをそれぞれ N と M としたとき、有効なマージ済みリストを作成できる方法の総数を求める必要があります。答えが非常に大きくなる場合は、10^9 + 7 で割った余りを返してください。例えば、入力が N = 5、M = 3 の場合、出力は 56 になります

この記事では、n個のボールからk個を選ぶすべての組み合わせについて「最大値 − 最小値」の差を求め、その合計を計算するPythonプログラムを紹介します。 問題の概要 n個のボールがあり、それぞれのボールには配列 nums の要素が番号として書かれています（nums[i] は i 番目のボールの番号）。これとは別に整数 k が与えられます。 各ターンでは、n個の異なるボールの中からk個を選び、そのk個の最大値と最小値の差を表に記録します。その後、選んだk個を元に戻し、考えられるすべての組み合わせに対して同じ操作を繰り返します。最後に、表に記録されたすべての差の合計を求めます。答えが非常に大き

配列 nums が与えられたとき、nums[i] = nums[j] を満たし、かつ i ≠ j であるようなペア（i, j）の個数を求めることを考えます。 たとえば入力が nums = [1, 3, 1, 3, 5] の場合、出力は 4 になります。該当するペアは (0, 2)、(2, 0)、(1, 3)、(3, 1) の4つだからです。 解法のアプローチ この問題は、各値の出現回数を集計してから組み合わせを計算することで、効率的に解くことができます。手順は以下の通りです。 出現回数を記録するための空の辞書（マップ）d を用意する nums の各要素 c について、すでに d に存在すれば

問題の概要配列 nums と整数 k が与えられたとき、「要素の総和が k で割り切れる」連続した部分列(サブ配列)の個数を求める問題です。例として、k = 3、nums = [1, 2, 3, 4, 1] という入力を考えてみましょう。この場合、条件を満たす部分列は [3]、[1, 2]、[1, 2, 3]、[2, 3, 4] の 4 つであるため、出力は 4 となります。アルゴリズムの考え方この問題は「累積和」と「剰余(モジュロ)」を組み合わせることで効率的に解けます。ポイントは次の通りです。先頭から順に累積和を計算し、その値を k で割った余りを記録していきます。異なる位置で同じ余りの累

問題の概要 m種類の文字と整数nが与えられたとき、これらの文字を使って構成できる「長さ2以上の回文（前から読んでも後ろから読んでも同じになる文字列）を部分文字列として含まない」長さnの文字列の個数を求める問題です。答えが非常に大きな値になる可能性があるため、109+7で割った余りを返します。 具体例で理解する 例として、n = 2、m = 3 のケースを見てみましょう。使用できる文字が {x, y, z} の3種類であるとき、理論上は [xx, xy, xz, yx, yy, yz, zx, zy, zz] の9通りの文字列が作れます。しかし、このうち [xx, yy, zz] は同じ文字が