Minimum Cost of Ropes
いくつかのロープがあり、ropes[i]はロープiの長さです。任意の2本のロープを1本にまとめることができ、その長さは2本の長さの合計になり、まとめるコストも同じ合計です。ロープが1本だけになるまで、まとめ続けます。
すべてのロープを1本にまとめるための合計コストの最小値を返すminCostRopesという名前の関数を書いてください。最初からロープが1本しかない場合は、0を返します。
関数
- ropesinteger-array
- 各ロープの長さ
- 戻り値integer
- すべてのロープを1本にまとめるための最小合計コスト
制約
1 ≤ ropes.length ≤ 1041 ≤ ropes[i] ≤ 100- 答えは32ビット符号付き整数に収まります。
例
- 入力
- ropes = [5, 2, 8, 3]
- 出力
- 33
- 説明
2と3をつないで5にし、長さ5の2本のロープをつないで10にし、次に8と10をつないで18にします。合計は5 + 10 + 18 = 33です。
- 入力
- ropes = [7]
- 出力
- 0
- 説明
- ロープは1本だけなので、結合は発生せず、費用もかかりません。
- 入力
- ropes = [1, 1, 1, 1]
- 出力
- 8
- 説明
1を2本ずつまとめてそれぞれ2のコストがかかり、次に長さ2の2本のロープをまとめて4のコストがかかります。合計で8です。各1を1本の伸びていくロープに加えると、コストは2 + 3 + 4 = 9になります。
発展問題
結合によって最大3本のロープをつなげ、そのコストがロープの長さの合計だとします。ロープの本数が割り切れない場合、貪欲法のルールはどのように変わりますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
合計コストを、元のロープごとの合計として表しましょう。1本のロープの長さは何回分支払われますか？
ロープの長さは、結合に参加するたびに一度支払われるため、最も長いロープはできるだけ少ない回数の結合に参加させるべきです。手元にある最も短い2本のロープを結合するのが、常に安全な最初の手です。
すべてのロープを最小ヒープに入れます。最も短い2本を取り出し、その合計をコストに加えて、合計をヒープに戻し、ロープが1本になるまで繰り返します。
解説
結合するたびに2本のロープの長さの合計分のコストがかかるため、早い段階で結合したロープは、その後に参加するすべての結合でも再びコストに含まれます。長いロープは早い段階で結合しないようにし、毎回、最も短い2本のロープを結合します。最小ヒープを使えば、その2本を O(log n) で見つけられます。
各ラウンドで最も短い2本を探す
正しいが、最大のテストでは終わらない
考え方
各ラウンドで、山を調べて最も短いロープを取り出し、もう一度調べて次に短いロープを取り出し、2本をつないだものを山に戻します。
なぜ最も短い2本なのか：ロープを葉とする木として、つなぎ合わせを描いてみましょう。ロープの長さは、そのロープより上にあるつなぎ合わせごとに1回ずつ加算されます。これはそのロープの深さにあたります。最も深い階層には、隣り合う2つの葉があります。最も短い2本のロープをそこに移しても、コストが増えることはありません。したがって、最もコストの低い方法の中には、最も短い2本を最初につなぐものがあり、この議論をより小さな山に対して繰り返せます。
2回の全走査を行うラウンドはn-1回あります：O(n²)で、ロープが10^4本なら、およそ10^8回の比較です。
アルゴリズム
- ロープを作業用リスト
pileにコピーし、totalを 0 に設定します。 - ロープが 1 本になるまで繰り返します。最も短いロープを見つけ、最後のロープをその位置に移動して取り除きます。
- 同じ操作をもう一度行い、次に短いロープを取得します。
- 2 本の長さの合計を
totalに加え、その長さのロープを山に追加します。 totalを返します。
def minCostRopes(ropes):
pile = list(ropes)
def take_shortest():
k = 0
for i in range(1, len(pile)):
if pile[i] < pile[k]:
k = i
pile[k], pile[-1] = pile[-1], pile[k] # move it to the end, then remove it
return pile.pop()
total = 0
while len(pile) > 1:
joined = take_shortest() + take_shortest()
total += joined
pile.append(joined)
return total最小ヒープ
考え方
最小ヒープでは、最短のロープがルートに保たれ、ルートの取り出しやロープの挿入には O(log n) のコストがかかります。1ラウンドでは、2回取り出して最短のロープを2本取得し、結合したロープを1回挿入します。
n 本のロープを結合するには、ヒープ操作をそれぞれ3回行う結合が n-1 回必要なので、時間計算量は O(n log n) です。10^4 本のロープなら、約 4 × 10^5 ステップです。ヒープに保持されるロープは最大でも n 本です。
アルゴリズム
- すべてのロープの長さを最小ヒープに入れ、
total = 0を設定します。 - ロープが1本になるまで繰り返します。最も短い2本を取り出します。
- その合計を
totalに加え、合計をヒープに戻します。 totalを返します。ロープが1本だけだった場合、値は0のままです。
import heapq
def minCostRopes(ropes):
heap = list(ropes)
heapq.heapify(heap) # a min-heap: heap[0] is the shortest rope
total = 0
while len(heap) > 1:
joined = heapq.heappop(heap) + heapq.heappop(heap)
total += joined
heapq.heappush(heap, joined)
return total
落とし穴と境界ケース
- 一度だけソートして、各ロープを1本の累積ロープに追加すること。累積ロープは、まだ使っていないロープより長くなる場合があります。
[2, 3, 4, 4]の場合、コストは 5 + 9 + 13 = 27 ですが、最短の2本を結合すると 5 + 8 + 13 = 26 です。 - 結合したロープを取り除くこと。その長さは山に戻され、後の結合で再びコストとして加算されます。
- 最後のロープの長さを返すこと。
[5, 2, 8, 3]の場合、最後のロープの長さは18ですが、コストは33です。 - 誤って最大ヒープを使うこと。C++ の
priority_queueと Rust のBinaryHeapは、順序を逆にしない限り最大値を取り出します。
よくある質問3
Minimum Cost of Ropes の時間計算量は何ですか？
O(n log n)時間、O(n)空間を最小ヒープで実現できます。n-1回の結合を行い、それぞれでO(log n)のヒープ操作を3回行います。最短のロープ2本を見つけるために山全体を走査すると、代わりにO(n²)になります。
ロープの最小コストはハフマン符号化と同じですか？
はい、同じアルゴリズムです。Huffman 符号化では、出現頻度が最も低い2つの記号を繰り返し結合して接頭符号を作り、各頻度に木の中での深さを掛けた値の合計を最小化します。ここでは、ロープが記号に、ロープの長さが出現頻度に相当するため、合計コストは同じ合計になります。
ロープの最小コスト問題はヒープを使わずに解けますか？
はい、キューを2つ使います。ロープを1つのキューにソートして並べ、結合したロープを2つ目のキューの末尾に追加します。結合したロープは非減少順に取り出されるので、残った最短のロープはどちらかのキューの先頭にあります。したがって、各ラウンドはO(1)で、長さが最大100なら計数ソートによって実行時間はO(n)になります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def minCostRopes(ropes):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
ropes = [5, 2, 8, 3]
期待される出力
33