Python

問題の概要整数型の配列 nums が与えられたとします。このとき、ある部分配列 [nums_l, nums_l+1, ..., nums_r-1, nums_r] の絶対和は、次のように定義されます。|nums_l + nums_l+1 + ... + nums_r-1 + nums_r|つまり、部分配列内の要素をすべて足し合わせた値の絶対値です。ここでの課題は、nums の任意の部分配列（空の部分配列も許容）の中から、絶対和が最大になるものを見つけ、その値を返すことです。入力例たとえば、入力が nums = [2, -4, -3, 2, -6] の場合を考えてみましょう。このとき出力は 11

問題の概要n 個のコースがあり、それぞれ 1 から n までの番号が付けられているとします。また、relations という配列が与えられ、relations[i] はペア (prevCourse_i, nextCourse_i) を含んでいます。これは「コース prevCourse_i を先に履修しなければ、コース nextCourse_i を履修できない」という前提関係を表します。さらに、最後のパラメータとして k が与えられます。1 学期あたり最大 k コースまで履修できますが、そのためには履修したいコースの前提科目を、前の学期までにすべて修了しておく必要があります。このとき、すべてのコ

問題概要 「a」「b」「c」の3種類の文字のみで構成された文字列 s が与えられます。この文字列に対して、以下のルールに従う操作を任意の回数(0回でも可)実行することを考えます。 すべての文字が同一である、空でない接頭辞(先頭部分)を選ぶ すべての文字が同一である、空でない接尾辞(末尾部分)を選ぶ 接頭辞と接尾辞は互いに重なっていてはならない 接頭辞と接尾辞を構成する文字は同じでなければならない 選んだ接頭辞と接尾辞の両方を文字列から削除する これらの操作を好きなだけ繰り返した後に残る文字列 s の最小の長さを求めるのが目的です。 例えば、入力が s = aabccabba の場合、出力は

3つの整数 a、b、c が与えられているとします。それぞれの値をサイズとする3つの石の山を使って、一人用のソリティアゲームを行います。各ターンでは、プレイヤーは異なる2つの空でない山を選び、それぞれから石を1つずつ取り除いて、スコアに1点を加算します。そして、空でない山が2つ未満になった時点でゲームは終了です。この記事では、取得可能な最大スコアを求める方法を解説します。 例として、入力が a = 4、b = 4、c = 6 の場合を考えてみましょう。このとき出力は 7 になります。初期状態は (4, 4, 6) であり、次の手順でゲームを進められるためです。 1番目と2番目の山から選ぶ →

問題の概要 2つの文字列 s と t が与えられます。次のルールに従って、新しい文字列「merge」を構築します。s または t のどちらか一方でも空でない限り、以下の操作のいずれかを選択して繰り返します。 s が空でない場合：s の先頭の1文字を merge の末尾に追加し、その文字を s から削除します。 t が空でない場合：t の先頭の1文字を merge の末尾に追加し、その文字を t から削除します。 最終的に、この方法で作成できる文字列の中から辞書順で最大のものを見つけます。 たとえば、入力が s = zxyxx、t = yzxxx の場合、出力は zyzxyxxxxx になり

2次元平面上の座標点を格納した配列 points があるとします。各要素は points[i] = (x_i, y_i) という形式で表され、点は x 座標の昇順にソートされているため、すべての 1 <= i < j <= 点数 について x_i < x_j が成り立ちます。さらに、整数値 k も与えられます。このとき、|x_i - x_j| <= k かつ 1 <= i < j <= 点数 を満たすすべての組み合わせの中から、方程式 y_i + y_j + |x_i - x_j| の最大値を求めるのが目的です。たとえば、入力が points =

文字列 s が与えられたとき、その中に含まれる「同種（homogenous）な部分文字列」の総数を求める問題を考えます。同種な文字列とは、構成するすべての文字が同一である文字列のことです。答えは非常に大きな値になる可能性があるため、10^9+7 で割った余りを返します。 問題の例 たとえば、入力が s = xyyzzzxx の場合、出力は 13 になります。同種の部分文字列は次のように数えられます。 x が 3 回 xx が 1 回 y が 2 回 yy が 1 回 z が 3 回 zz が 2 回 zzz が 1 回 したがって、(3 + 1 + 2 + 1 + 3 + 2 + 1) =

nums という配列があり、i 番目の要素は nums[i] 個のボールが入った袋を表しているとします。さらに、mx という別の値も与えられます。この mx は、以下の操作を実行できる最大回数を意味します。任意のボールの入った袋を1つ選び、少なくとも1個ずつのボールが入った2つの新しい袋に分割する。ここで「ペナルティ」とは、すべての袋の中で最も多くのボールが入っている袋のボール数を指します。私たちの目的は、操作を最大 mx 回まで行った後のペナルティを最小化すること、すなわち実現可能な最小のペナルティを求めることです。例えば、入力が nums = [4,8,16,4]、mx = 4 の場合、出

非常に大きな整数を表す文字列 num と、整数 k が与えられているとします。隣接する2つの桁を入れ替える操作を最大 k 回まで行えるとき、実現できる最小の値を求める必要があります。 たとえば、入力が num = 5432、k = 4 の場合、出力は 2453 になります。最初の数は 5432 ですが、1回目の交換で 4532、続いて 4523、次に 4253、そして最終的に 2453 となります。 アルゴリズムの考え方 この問題は貪欲法（グリーディ法）で効率的に解けます。左端の桁から順に、「残りの交換回数 k で移動できる範囲内に存在する最も小さい数字」をその位置へ引き寄せます。これを繰

2次元配列 groups と、別の1次元配列 nums が与えられているとします。このとき、nums から互いに重ならないn個の部分配列を選び出せるかどうかを判定します。条件として、i番目の部分配列は groups[i] と完全に一致すること、また i > 0 の場合は (i-1) 番目の部分配列が nums 内で i 番目より先に現れることが求められます。 例えば、入力が groups = [[2,-2,-2],[4,-3,0]]、nums = [1,-1,0,2,-2,-2,4,-3,0] の場合、出力は True になります。これは、groups[0] が nums のインデックス

2人のプレイヤーAmalとBimalがゲームを行い、Amalが先手です。最初、山にはn個の石が積まれています。各プレイヤーは自分のターンに、山から「平方数（0以外）」個の石を取り除かなければなりません。そして、これ以上手を打てなくなったプレイヤーが負けとなります。nが与えられたとき、Amalがこのゲームに勝てるかどうかを判定しましょう。 例えば、n = 21の場合、答えは True になります。Amalが最初に16個の石を取ると、Bimalは4個取り、最後にAmalが残りの1個を取って勝利できるからです。 解法のアプローチ この問題は動的計画法（DP）で効率よく解けます。dp[i] を「i個

複数の家の座標点を含むリストが与えられたとします。(xc, yc) の位置にサービスセンターを設置するとき、すべての点から (xc, yc) までのユークリッド距離の合計が最小になるようにしたいと考えます。つまり、この問題では最小となる距離の合計を求める必要があります。たとえば、入力が positions = [(10,11),(11,10),(11,12),(12,11)] の場合、出力は 4.0 になります。解決のアプローチ：三分探索（Ternary Search）この問題は三分探索を用いて効率的に解くことができます。「全点とのユークリッド距離の合計」という目的関数は下に凸な関数であるため

問題概要小文字の英字のみで構成された文字列 s が与えられたとき、次の2つの条件を満たす「空でない部分文字列」の最大個数を求めます。選んだ部分文字列同士は互いに重ならない(オーバーラップしない)ある部分文字列が特定の文字 ch を含むなら、その文字 ch の出現箇所をすべて含まなければならないさらに、条件を満たす解が複数存在して部分文字列の個数が同じ場合は、合計長が最小になる解を返します。入力例と出力例たとえば、入力が s = pqstpqqprrr の場合、出力は [s, t, rrr] となります。条件を満たす候補としては pqstpqqprrr、pqstpqqp、st、s、t、rrr が

問題の概要「boxes」というバイナリ文字列（0と1のみで構成される文字列）があるとします。boxes[i] が 0 の場合は i 番目のボックスが空であることを、1 の場合はそのボックスにボールが 1 個入っていることを意味します。1 回の操作では、あるボックスから隣接するボックスへボールを 1 個移動できます。操作の結果、1 つのボックスに複数のボールが入っても構いません。ここで、サイズ n の配列 answer を求めます。answer[i] は、すべてのボールを i 番目のボックスに集めるために必要な最小操作回数です。たとえば、入力が boxes = 1101 の場合、出力は [4,

問題の概要正の値からなる配列 target が与えられているとします。また、同じサイズで、すべての要素が0である配列 initial も用意します。このとき、次の操作を繰り返して initial を target に一致させるために必要な最小の操作回数を求めます。操作の定義： initial から任意の部分配列（連続する区間）を選び、その範囲内の各要素の値を1ずつ増やします。具体例入力が target = [2,3,4,3,2] の場合、出力は 4 になります。手順は以下の通りです。最初、配列は [0,0,0,0,0] です。インデックス0〜4を選んで1増やす → [1,1,1,1,1]再びイ

問題概要サイズ n の配列 nums と、サイズ m の配列 multipliers(n ≥ m)が与えられます。配列は1始まりのインデックスで扱い、初期スコアは0です。ここで、ちょうど m 回の操作を行います。i 番目の操作(1始まり)では、次の処理を実行します。nums の先頭または末尾から値 x を1つ選ぶmultipliers[i] × x をスコアに加算するx を nums から取り除くm 回の操作をすべて終えた時点での最大スコアを求めるのが目標です。たとえば、nums = [5, 10, 15]、multipliers = [5, 3, 2] が入力された場合、出力は 115 にな

問題概要 文字列 s と整数 k が与えられます。s から最大 k 文字を削除し、削除後の文字列をランレングスエンコーディング（連長圧縮）したとき、その長さが最小になるようにしたい、というのが本記事のテーマです。 ランレングスエンコーディングとは、連続して現れる同一文字（2 回以上の繰り返し）を「文字＋繰り返し回数」の形式に置き換える文字列圧縮手法です。たとえば "xxyzzz" という文字列の場合、"xx" は "x2" に、"zzz" は "z3" に置き換えられ、圧縮結果は "x

2つの配列 nums1 と nums2 が与えられているとします。「有効なパス」は次のように定義されます。nums1 または nums2 のいずれかを選択し、インデックス0から走査を開始する。配列を左から右へ向かって進む。移動中に、nums1 と nums2 の両方に存在する共通の値に出会った場合は、その時点でパスをもう一方の配列へ切り替えることができます。スコアとは、有効なパス上の一意な値の合計のことです。ここでの課題は、考えられるすべての有効なパスの中から得られる最大スコアを求めることです。答えが大きすぎる場合は、結果を 10^9+7 で割った余りを返してください。たとえば、入力が num

数値文字列 s が与えられたとします。ここで「素晴らしい部分文字列（awesome substring）」とは、s の空でない部分文字列のうち、文字の入れ替え（スワップ）を何度行ってもよいとして回文にできるものを指します。この記事では、s に含まれる最長の素晴らしい部分文字列の長さを求める方法を解説します。例えば、入力が s = 4353526 の場合、出力は 5 になります。「35352」が最長の素晴らしい部分文字列であり、文字を並べ替えることで「35253」という回文を作れるからです。回文にできる条件とは？文字を自由に入れ替えられる場合、ある文字列が回文にできるかどうかは、各文字の出現回数

問題概要 整数 n と配列 cuts が与えられます。長さ n 単位の木棒があり、両端には 0 から n までの目盛りが付けられています。cuts[i] は棒を切断できる位置を表します。切断はどのような順序でも実行できますが、1回の切断にかかるコストは「その瞬間に切断する木棒の長さ」であり、全体のコストはすべての切断コストの合計です。合計コストが最小になるように切断順序を選んだときの最小コストを求めます。 具体例 n = 7、cuts = [5, 1, 4, 3] の場合、答えは 16 になります。たとえば切断順序を [3, 5, 1, 4] とすると、以下のように進みます。 まず長さ 7