Python

複数のバケットと x 個のボールが与えられたとします。ボールをバケットに入れると、ボール同士の間に特別な力が働き、「2つのボール間の最小力」を最大化するような配置を見つける必要があります。位置 p と q にある2つのボール間の力は |p − q| で表されます。入力として、バケットの位置を格納した配列とボールの個数 x が与えられ、その中で実現できる最小力を求めます。 例えば、入力が pos = [2, 4, 6, 8, 10, 12]、x = 3 の場合、出力は 4 になります。 この場合、3つのボールをそれぞれ位置 4、8、12 に置くことで、ボール間の力は 4 になります。これ以上こ

問題の概要 配列 nums と整数 k が与えられたとき、nums からサイズ k の「最も競争力のある」部分列を求めます。ここで、ある部分列 s1 が同じサイズの別の部分列 s2 より競争力が高いとは、s1 と s2 が初めて異なる位置において、s1 の数値が s2 の対応する数値よりも小さいことを意味します。 例えば、入力が nums = [4,6,3,7]、k = 2 の場合、出力は [3,7] となります。サイズ 2 のすべての部分列 {[4,6], [4,3], [4,7], [6,3], [6,7], [3,7]} の中で、[3,7] が最も競争力の高い部分列だからです。 解法アプ

問題の概要同じ長さを持つ2つの文字列 a と b があるとします。あるインデックスを1つ選び、その位置で両方の文字列を同時に分割します。すると、a は前半部分 a_pref と後半部分 a_suff に(a = a_pref + a_suff)、b も同様に b_pref と b_suff に(b = b_pref + b_suff)分けられます。このとき、「a_pref + b_suff」または「b_pref + a_suff」という組み合わせのどちらかが回文(前から読んでも後ろから読んでも同じ文字列)になるかどうかを判定するのが目的です。なお、分割位置によっては片方が空文字列になっても構い

問題の概要 長さが偶数の配列 nums と整数 limit が与えられるとします。1回の操作では、nums 内の任意の要素を、1 以上 limit 以下の範囲の別の値に置き換えることができます。そして、すべてのインデックス i について nums[i] + nums[n-1-i] が常に同じ値になるとき、この配列は相補的（complementary）であると定義されます。この記事では、配列 nums を相補的な状態にするために必要な最小の操作回数を求める方法を解説します。 具体例 たとえば、入力が nums = [1,4,2,3]、limit = 4 の場合を考えてみましょう。このとき出力は

数列 nums と、サイズ m の2つの配列 l および r が与えられます。l と r は [l[i], r[i]] のような範囲クエリを表しています。ここで求めたいのは、ブール値のリスト ans です。ans[i] は、nums[l[i]] から nums[r[i]] までの部分配列を並べ替えて等差数列(算術数列)を作れる場合に True、そうでない場合に False となります。 等差数列とは、少なくとも2つの要素から構成され、隣接する2つの要素同士の差がすべて等しい数列のことです。たとえば、[2, 4, 6, 8, 10]、[5, 5, 5, 5]、[4, -2, -8, -14]

問題の概要さまざまな高さの n 棟の建物が一列に並んでおり、パルクール選手がレンガとはしごを使って隣の建物へ移動していく状況を考えてみましょう。各建物の高さは配列として与えられます。レンガ1枚の高さは1単位で、手持ちの枚数も決まっています。レンガとはしごはそれぞれ1回しか使用できません。このとき、パルクール選手が到達できる最も遠い建物のインデックスを求めるのが課題です。例として、次の入力を見てみましょう。heights = [5, 8, 7, 6, 2, 3, 1, 4]bricks（レンガ） = 3ladders（はしご） = 2この場合の出力は 7 となります。移動の手順選手はまず建物 0

問題の概要 ここに inventory という配列があるとします。inventory[i] は、i 番目の色のボールの初期在庫数を表します。さらに、顧客が購入したいボールの総数を表す値 orders も与えられます。ボールはどの順序でも販売でき、顧客はどんな色のボールでも受け入れます。 このボールの価値には特別なルールがあります。各色のボールの価値は、「その色のボールが現在インベントリに何個残っているか」に等しくなります。たとえば、現在青いボールが6個ある場合、最初の1個は価格6で売れ、残りが5個になるため、次の青いボールは価格5で売れることになります。この条件のもとで、orders 個のボー

問題の概要s と t の2種類の文字のみで構成された文字列 s があるとします。この文字列を「バランスの取れた状態」にするために、任意の数の文字を削除することができます。ここで、文字列 s がバランスしているとは、i < j を満たすインデックスのペア (i, j) であって、s[i] = t かつ s[j] = s となるものが存在しない状態を指します。つまり、t の後に s が現れることがない状態です。私たちの目的は、s をバランスさせるために必要な最小の削除回数を求めることです。入力例例えば、入力が s = sststtst の場合、出力は 2 になります。これは次のいずれかの操作

問題の概要 4つのゴンドラを備えた観覧車を考えます。各ゴンドラには最大4人の乗客が乗ることができ、観覧車は反時計回りに回転します。1回転させるごとに「run」の運転コストがかかります。 ここで、n個の要素を持つ配列「cust」が与えられます。各要素 i は、i 回目の回転の前に観覧車の乗車を待っている人数を表します。乗客は乗車の際に「board」の料金を支払い、この料金は観覧車の反時計回り1回転分に相当します。列に並んでいる人は、どれかのゴンドラに空席があればそこへ優先的に案内され、無駄に待たされることはありません。 与えられたデータをもとに、利益を最大化できる最小の回転数を求めるのがこの問

問題概要 「forbidden」という配列が与えられます。forbidden[i] は、虫(バグ)がその位置 forbidden[i] へジャンプしてはいけないことを示します。さらに、a、b、x という3つの値も与えられます。虫の家は数直線上の位置 x にあり、虫は初期状態で位置 0 にいます。虫は以下のルールに従ってジャンプできます。 正確に a だけ前(右)方向へジャンプできる 正確に b だけ後ろ(左)方向へジャンプできる 後ろ向きのジャンプを2回連続で行うことはできない 配列 forbidden に含まれる位置にはジャンプできない 家より先へ前方向にジャンプすることは可能だが、負の位

ある家族には、父親、その子どもたち、そして祖母といったように、異なる世代のメンバーが属しています。現実の家庭と同じように、この家族にも出生と死亡が絶えず起こります。家族の中で最も年長のメンバーが「家長」とみなされます。家長が亡くなると、その直系の後継者、つまり子どもが新たな家長となります。ここでは3つの関数を実装します。1つ目はbirth()：家族に子どもが生まれたときに呼び出され、親の名前と子どもの名前を受け取って記録に追加します。2つ目はdeath()：家族に死亡者が発生したときに呼び出され、故人の名前を受け取って記録から除外します。3つ目はinheritance()：呼び出されるたびに、

問題の概要n個の点が(x, y)という形式で与えられているとします。「垂直領域」とは、y軸方向に無限に延びる領域のことです。この問題では、他のどの点も内部に含まず、かつ最も幅が広い2点間の垂直領域を見つける必要があります。入力例例えば、入力が pts = [[10,9],[11,11],[9,6],[11,9]] の場合、出力は 1 となります。下図の赤と青で示された領域が最適解であり、これらの領域内には点が一切存在しません。解法のアプローチこの問題は、以下の手順で解くことができます。リスト pts をソートします。i を 1 から pts のサイズまで繰り返し処理します。(pts[i][0]

問題の概要2つの文字列 s と t が与えられたとき、この2つが「近い(close)」関係にあるかどうかを判定するプログラムを考えます。次の2種類の操作を何度でも繰り返し適用することで、一方の文字列からもう一方の文字列を作り出せる場合、その2つの文字列は「近い」とみなされます。既存の2文字を入れ替える:文字列内の任意の2文字の位置を交換できます。例:abcde → aecdbある文字の出現箇所をすべて別の文字に変換する(同時に逆変換も行う):すべての a を b に、すべての b を a に変換するといった操作が可能です。例:aacabb → bbcbaa(ここではすべての a が b に、b

本記事では、キューの先頭（フロント）・中央（ミドル）・末尾（バック）の3箇所から値を追加（push）および削除（pop）できるデータ構造を、Pythonで実装する方法を解説します。さらに、任意の時点でのキュー全体の状態を確認できる関数も併せて実装します。 実装する機能一覧 今回作成するクラスは、以下の7つのメソッドを持つ必要があります。 push_from_front(value)：キューの先頭に値を追加する push_from_middle(value)：キューの中央に値を追加する push_from_back(value)：キューの末尾に値を追加する pop_from_front()：

問題概要 m × n のグリッドボックスを考えます。各セルには、左上から右下、もしくは右上から左下へ向けて斜めの板が設置されています。グリッドの上端からボールを落とし、それぞれのボールが底まで到達できるか、そしてどの列に着地するのかを求めるのがこの問題です。 グリッドは行列として与えられ、各セルの値は板の向きを表します。 1: 左上から右下へ下る斜めの板 -1: 右上から左下へ下る斜めの板 n 個のボールを上端の各列から順に落としたとき、底に到達したボールの着地列を答えとして返します。途中で側面の壁に当たったり、V字型の溝にはまって動けなくなったボールについては -1 を出力します。 3

問題の概要小さな町に m 軒の家があるとします。各家庭は n 色（1〜n のラベル付き）のうちどれか一色で塗らなければなりませんが、すでに塗装済みの家もあり、その場合は塗り直す必要はありません。同じ色で塗られた連続する家のまとまりを「街区（neighborhood）」と呼びます。入力として与えられるデータは次のとおりです。houses[i]：i 番目の家の色。値が 0 の場合はまだ塗装されていないことを表します。costs[i][j]：i 番目の家を色 j+1 で塗るときのコスト（2次元配列）。target：最終的に作りたい街区の数。求めるのは、残りの家をすべて塗装した結果、街区の数がちょうど

問題の概要家の位置を表す配列 houses と整数 k が与えられます。houses[i] は一本の通り沿いにある i 番目の家の位置を示しており、この通りに k 個のメールボックスを設置することを考えます。このとき、各家から最寄りのメールボックスまでの距離の合計が最小になるような設置場所を求めるのが目的です。たとえば、入力が houses = [6,7,9,16,22]、k = 2 の場合を考えてみましょう。メールボックスを位置 7 と 18 に設置すると、各家からの最短距離の合計は次のように計算できます。|6−7| + |7−7| + |9−7| + |16−18| + |22−18| =

n個のノード(0からn-1までの番号が振られている)からなる木を考えます。この木はparent配列によって表現され、parent[i]はノードiの親ノードを示します。木の根はノード0です。ここで、指定されたノードのk番目の祖先を求めるプログラムを作成します。該当する祖先が存在しない場合は-1を返します。例えば、次のような木が与えられたとします。この場合の出力は2になります。ノード6の1番目の祖先は5であり、2番目の祖先は2だからです。解法のアプローチこの問題は「バイナリリフティング(ダブリング)」と呼ばれる技法を使うことで効率的に解けます。kを2の冪乗の組み合わせに分解することで、親をたどる回

問題の概要 頂点 0 から n − 1 までの番号が付いた n 個の頂点を持つ無向グラフが与えられ、各辺には重みが設定されているものとします。このグラフをもとに、最小全域木(MST)に含まれる「クリティカルエッジ」と「疑似クリティカルエッジ」を特定します。 クリティカルエッジとは、その辺を削除すると MST の総重みが増加してしまう辺のことです。一方、疑似クリティカルエッジとは、すべての MST に必ず含まれるわけではないものの、何らかの MST には現れ得る辺のことです。ここでは、入力として与えられたグラフに対して、該当する辺のインデックスを求めます。 たとえば、次のようなグラフが入力とし

問題の概要 正整数からなる配列 candiesCount が与えられ、candiesCount[i] は i 番目の種類のキャンディーの在庫数を表しているとします。さらに、各要素が [favoriteType_i, favoriteDay_i, dailyCap_i] の3つの値を持つ配列 queries も与えられます。 キャンディーを食べるときは、次のルールを守らなければなりません。 0日目からキャンディーを食べ始めます。 i 番目の種類のキャンディーは、それより前の i−1 種類をすべて食べ終えるまで食べられません。 すべてのキャンディーを食べきるまで、毎日必ず1個以上のキャンディーを