Python

台所に n 個のオレンジがあるとしましょう。私たちは毎日、次の3つのルールの中から必ず1つだけを選んでオレンジを食べます。 ルール1：オレンジを1個食べる ルール2：n が偶数なら、n / 2 個食べる ルール3：n が3で割り切れるなら、2 × (n / 3) 個食べる このとき、n 個すべてのオレンジを食べ切るまでに必要な最小の日数を求めるのがこの問題です。 具体例：n = 10 の場合 入力が n = 10 のとき、答えは 4 になります。実際の進め方は以下の通りです。 1日目：1個食べる → 残り 10 − 1 = 9 個 2日目：6個食べる（2 × (9 / 3)）→ 残り 9

m × n のサイズを持つ文字からなる2次元配列 grid があるとします。このグリッドの中にサイクル(閉路)が存在するかどうかを判定する必要があります。ここでいうサイクルとは、長さ4以上の経路で、開始位置と終了位置が同じセルになるものを指します。移動は上・下・左・右の4方向に行えますが、移動先のセルは現在のセルと同じ値を持っている必要があり、また一度訪れたセルを再訪することはできません。 たとえば、入力が以下のような場合を考えてみます。 mmmpmkmmmmsmfmmm この場合の出力は True になります。緑色のセルはすべて文字「m」で構成されており、外周に沿って一周するループ状の経路(

n個の頂点（0からn-1までの番号が付けられたもの）から構成される無向グラフが与えられます。各辺には重みが設定されており、重みは「1」「2」「3」の3種類があります。このグラフを移動できるのはJackとCaseyの2人で、Jackは重み1の辺のみ、Caseyは重み2の辺のみを移動でき、重み3の辺は両方が移動できます。 ここで、JackとCaseyの両方がグラフ内のすべての頂点に到達できるようにするために、不要な辺を削除することを考えます。このとき削除が必要な辺の本数を求め、どのようにしても移動可能な状態にできない場合は-1を返します。 例えば、入力が次のような場合を考えてみましょう。 n =

問題の概要2つの数字のみで構成された文字列 s と t が与えられます。次の操作を何度でも繰り返し適用して、文字列 s を文字列 t に変換できるかどうかを判定するプログラムを作成します。操作の定義： s の中から空でない部分文字列を1つ選び、その範囲内の文字を昇順（小さい順）に並べ替えます。例として、s = 95643、t = 45963 の場合、出力は True になります。実際に次のような手順で変換できるためです。95643 → 95463 → 45963解法のアプローチこの問題は、以下の手順で解くことができます。各数字（0〜9）ごとに、その数字が s 内に出現する位置インデックスを記録

問題の概要 いくつかの石が一列に並んでおり、各石には数値が割り当てられています。これらの数値は配列 stoneValue として与えられます。各ラウンドでは、まず Amal が石の列を2つの部分に分割し、続いて Bimal がそれぞれの部分の値（その部分に含まれる全石の合計値）を計算します。そして Bimal は値が大きい方の部分を捨て、Amal のスコアは残った部分の値だけ増加します。両部分の値が等しい場合は、どちらを捨てるかを Amal が自由に決められます。次のラウンドは残った部分から始まり、石が1つだけ残った時点でゲーム終了です。Amal が獲得できるスコアの最大値を求めてください。

問題の概要 nums という整数の配列と、もう一つの値 k が与えられます。1 回の操作では、合計が k に等しくなる 2 つの要素を nums から選び、それらを配列から取り除くことができます。ここでの課題は、この操作を実行できる最大回数を求めることです。 たとえば、入力が nums = [8,3,6,1,5]、k = 9 の場合、答えは 2 になります。これは、まず合計が 9 になる [3,6] を削除でき、その後同じく合計が 9 になる [8,1] も削除できるためです。残った要素は [5] だけとなり、これ以上操作は行えません。 解決のアプローチ この問題は、各値の出現回数をカウント

問題の概要 n 個の要素を持つ配列 baseCosts（アイスクリームのベースの価格一覧）と、m 個の要素を持つ配列 toppingCosts（トッピングの価格一覧）、そして目標金額 target が与えられます。次のルールに従ってデザートを作ります。 ベースは必ずちょうど1つ選ぶ。 トッピングは1種類以上追加してもよいし、まったく追加しなくてもよい。 同じ種類のトッピングは最大2つまで使用できる。 baseCosts[i] は i 番目のアイスクリームベースの価格、toppingCosts[i] は i 番目のトッピング1つの価格を表します。target はデザートの目標価格です。合計コ

問題概要 整数 n が与えられたとき、1 から n までの各数値を2進数表現に変換し、それらを順番に連結してできる2進文字列の10進数としての値を求めます。答えが非常に大きくなる場合は、109 + 7 で割った余りを返します。 例えば、n = 4 の場合を考えてみましょう。1 から 4 までの2進数表現を順に連結すると、次のようになります。 1 + 10 + 11 + 100 = 110111000 この2進数「110111000」を10進数に変換すると 220 になります。これが求める答えです。 解法のアプローチ この問題は、以下の手順で解くことができます。 答え ans を 1 で初期

問題の概要 nums1 と nums2 という2つの整数配列が与えられます。各配列の要素はすべて 1〜6 の範囲の値です。1回の操作では、どちらかの配列内の任意の要素を、1〜6 の範囲内の任意の値に書き換えることができます。 このとき、nums1 の要素の合計と nums2 の要素の合計を一致させるのに必要な最小の操作回数を求めます。どうしても一致させられない場合は -1 を返してください。 例えば、入力が nums1 = [1, 5, 6]、nums2 = [4, 1, 1] の場合、答えは 2 になります。実際、次のように2回の操作で合計を揃えられます。 1回目:nums2 を [4,

問題の概要 非減少順(昇順)にソートされた整数配列 nums が与えられます。ここで、nums と同じ長さを持つ配列 result を作成し、result[i] には nums[i] と配列内の他のすべての要素との絶対差の合計を格納することを考えます。 たとえば、入力が nums = [5, 7, 12] の場合、出力は [9, 7, 12] となります。これは次のように計算されます。 |5−5| + |5−7| + |5−12| = 0 + 2 + 7 = 9 |7−5| + |7−7| + |7−12| = 2 + 0 + 5 = 7 |12−5| + |12−7| + |12−12|

ランプ（ramp）とは？ 整数の配列 nums が与えられたとき、「ランプ」とは i < j かつ nums[i] <= nums[j] を満たすインデックスのペア (i, j) のことです。ランプの幅は j − i で表されます。この記事では、nums に含まれるランプの中で最大の幅を求める方法を解説します。条件を満たすペアがひとつも存在しない場合は 0 を返します。 例として、nums = [6,0,8,2,1,5] という入力を考えてみましょう。この場合の出力は 4 になります。(i, j) = (1, 5) のとき nums[1] = 0、nums[5] = 5 となり、条

問題の概要Amal（アマル）とBimal（ビマル）がゲームをしていて、Amalが先手であるとします。このゲームは以下のようなルールです。山の中にn個の石があります。各プレイヤーは順番に山から1個の石を取り、その石の位置に応じたポイントを受け取ります。ただし、AmalとBimalは同じ石を異なる価値で評価する場合があります。同じ長さを持つ2つの配列 A_Values と B_Values が与えられます。A_Values[i] と B_Values[i] は、それぞれi番目の石に対するAmalとBimalの評価値を表します。すべての石が取り終わった時点で、合計スコアが高い方が勝者となります。スコ

問題の概要 文字列形式で与えられた数値 n があるとします。このとき、その合計が n と等しくなるような「デシバイナリ数」の最小個数を求める必要があります。デシバイナリ数とは、各桁が 0 または 1 のみで構成される十進数のことです。 例えば、入力が n = 132 の場合、出力は 3 になります。これは、132 が 3 つのデシバイナリ数(10 + 11 + 111)の合計として表せるためです。 解法のアプローチ この問題を解く鍵は、答えが n の中で最も大きい桁の数字になるという点に気づくことです。 なぜなら、ある桁の数字が d である場合、その桁の合計を d にするには少なくとも d 個

問題の概要 ある整数 n が与えられたとき、その数を互いに異なる3の累乗の和として表すことができるかどうかを判定するのが、この記事のテーマです。 ここでいう「3の累乗」とは、y = 3ⁿ(x は整数)と書ける数のことです。具体的には 1(3⁰)、3(3¹)、9(3²)、27(3³)、81(3⁴)… といった数値が該当します。 入力例と出力例 たとえば n = 117 の場合を見てみましょう。 117 = 3⁴ + 3³ + 3² = 81 + 27 + 9 このように異なる3の累乗だけで表せるため、答えは True となります。 解き方：大きい累乗から順に引いていく貪欲法 この問題は、大き

問題概要左から i 番目の石の価値が stones[i] で表される配列 stones があるとします。Amal（アマル）と Bimal（ビマル）という2人のプレイヤーが、この石を使って交互にターン制のゲームを行います。石は合計 n 個が一列に並んでおり、必ず Amal が先手です。各プレイヤーは自分のターンに、列の左端または右端の石を1つ取り除き、残った石の価値の合計を得点として獲得します。最終的に高いスコアを取った方が勝者です。ここで Bimal は、このゲームでは自分が常に負けてしまうことに気づき、スコアの差をできるだけ小さくする戦略を選ぶことにしました。一方、Amal はスコアの差を最

問題の概要 文字列 s が与えられたとき、そのすべての部分文字列について「美しさ（beauty）」を計算し、その合計を求めることを考えます。 ここでいう文字列の「美しさ」とは、最も出現頻度の高い文字と最も出現頻度の低い文字の出現回数の差のことです。たとえば文字列 abaacc の場合、最頻文字は a（3回）、最稀文字は b や c（各1回）なので、美しさは 3 − 1 = 2 となります。 具体例 入力が s = xxyzy の場合、出力は 5 になります。これは、美しさが 0 以外になる部分文字列が [xxy, xxyz, xxyzy, xyzy, yzy] の5つであり、それぞれの美しさが

問題の概要 正の整数のみを含む配列 nums が与えられます。この中から要素がすべて一意（重複なし）である部分配列をちょうど1つ選んで「消去」し、その部分配列に含まれる要素の合計値をスコアとして得ます。求めたいのは、この操作で取得できるスコアの最大値です。 例えば、入力が nums = [6,3,2,3,6,3,2,3,6] の場合、出力は 11 になります。これは、最適な部分配列が [6,3,2] または [2,3,6] のいずれかであり、どちらも合計が 11 になるためです。 解き方のアプローチ：スライディングウィンドウ この問題はスライディングウィンドウ（尺取り法）を使うことで効率的に

nums という整数配列と、limit・goal という2つの値が与えられているとします。この配列は特殊な条件を満たしており、すべてのインデックス i(0 から配列サイズ − 1 まで)に対して |nums[i]| ≤ limit が成立しています。ここでの課題は、配列全体の合計が goal と一致するようにするために、追加で挿入すべき要素の最小個数を求めることです。なお、新たに追加する要素についても、その絶対値が limit を超えてはいけません。 例として、nums = [2,-2,2]、limit = 3、goal = -4 が入力された場合を考えてみましょう。この場合の出力は 2 にな

問題の概要 nums という整数型の配列と、値 k が与えられているとします。プレイヤーはインデックス 0 からスタートし、1 回の移動につき、配列の境界外に出ない範囲で最大 k ステップだけ右へジャンプできます。目標は、配列の最後のインデックスに到達することです。 ジャンプによって得られるスコアは、「訪れたすべてのインデックス j における nums[j] の合計」です。このとき、取得できるスコアの最大値を求める必要があります。 たとえば、入力が nums = [1, -2, -5, 7, -6, 4]、k = 2 の場合、出力は 10 になります。[1, -2, 7, 4] の順にジャン

無向の重み付き連結グラフがあるとします。グラフは n 個のノードを持ち、それぞれのノードには 1 から n までのラベルが付けられています。始点から終点へのパスとは [z0, z1, z2, ..., zk] のようなノードの列のことで、z0 が始点ノード、zk が終点ノードであり、隣り合うノード zi と zi+1 の間（0 ≤ i ≤ k-1）には必ず辺が存在します。パスの距離は、そのパスが通る辺の重みの総和として定義されます。また、dist(x) は「ノード n からノード x までの最短距離」を表すものとします。制限付きパス（restricted path）とは、すべての i（0 ≤