トップ > AtCoder > ABC252F - Bread

ABC252F - Bread

AtCoder AtCoder-Beginner Contest マージテク 逆順に考える Python

考え方

分割の過程を二分木だと思って逆順に見ると，各葉に起因するコストは(葉の長さ)×(葉の深さ)となる．

よって，もし二分木の形が決まっているのなら，長さが小さいものが最も深くなるように配置すれば良い．


以上をもとに，テキトーにつくった（分割過程を表す）二分木のコストを作り変え，最小化する手順を考える．これは，

  1. コストが最小の2つが二分木の最深部に位置するように並び替える
  2. ↑の2つの葉の親を新たな葉と考え直す
  3. 以下同じ
とすればよい．

よって，バラバラの状態から考えて，一番小さい2つを順にくっつけていけばよい．

（ちゃんと示すなら帰納法を使うが，実際の発見手順はこんな感じ？）

回答例

from heapq import heappop, heappush, heapify

N, L = map(int, input().split())
A = list(map(int, input().split()))

SUM = sum(A)
if SUM < L:
    A = A + [L - SUM]
heapify(A)

ans = 0
while len(A) > 1:
    x = heappop(A)
    y = heappop(A)
    ans += x + y
    heappush(A, x + y)

print(ans)

参考