問題
$N$ 個のシンボルの出現頻度 $f_1,\dots,f_N$ が与えられる。ハフマン符号を構築するときの符号長の重み付き総和（総マージコスト）の最小値を求めよ。頻度の集合から2つを選んで足し合わせ（そのコストを加算し）、新しい要素として集合に戻す操作を、要素が1個になるまで繰り返す。
制約
| パラメータ | 範囲 | 備考 |
|---|---|---|
| $N$ | $1 \le N \le 10^5$ | シンボル数 |
| $f_i$ | $1 \le f_i \le 10^9$ | 出現頻度 |
入出力例
入力例1
4
1 2 3 4出力例1
19$1+2=3$（コスト3）→$\{3,3,4\}$→$3+3=6$（累計9）→$\{4,6\}$→$4+6=10$（累計19）。
入力例2
1
100出力例2
0概念図
ヒント
ヒント1（方向性）
毎回2つを選んで合体させ合計コストを最小化する問題は、常にその時点で最小の2つを選ぶのが最適（貪欲法）。木の深さとの関係から理由を考えよ。
ヒント2（アプローチ）
「その時点の最小値」を高速に取り出すには優先度付きキュー（最小ヒープ）を使う。heapqで毎回2つ取り出し、和をコストに加算し再度ヒープに戻す。
ヒント3（ほぼ答え）
import heapq
heapq.heapify(freq)
total_cost = 0
while len(freq) > 1:
x = heapq.heappop(freq)
y = heapq.heappop(freq)
merged = x + y
total_cost += merged
heapq.heappush(freq, merged)
print(total_cost)模範解答
import sys
import heapq
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
freq = list(map(int, data[1:1 + n]))
heapq.heapify(freq)
total_cost = 0
while len(freq) > 1:
x = heapq.heappop(freq)
y = heapq.heappop(freq)
merged = x + y
total_cost += merged
heapq.heappush(freq, merged)
print(total_cost)
main()計算量: ヒープ操作が $N-1$ 回、各操作 $O(\log N)$ で全体 $O(N\log N)$。
Step-by-Step 解説
Step 1: 最小ヒープの構築
heapq.heapify(freq)で$O(N)$で最小ヒープに変換。
Step 2: 最小2要素を取り出してマージ
heappopを2回呼び、最小の2つを取得。ハフマン木の新しい内部ノードに対応。
Step 3: マージコストを加算しヒープへ戻す
合体後の値は「このマージのコスト」であり同時に「新しい仮想シンボルの頻度」でもある。
Step 4: 要素が1個になるまで繰り返す
累積したtotal_costが答え。頻度最小のシンボルほど深い位置に置くのが最適という交換論法で証明できる。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 毎回全体をソートし直す（$O(N^2\log N)$） | 配列のソートを使い回す | heapqで$O(N\log N)$に |
| N=1で誤動作 | while len(freq)>1を書き忘れる | N=1ならループ0回で0のまま正しく終了 |
| マージ後の値をヒープに戻し忘れる | 2要素popだけで満足 | heappush(freq, merged)を忘れない |
初期コストをsum(freq)にする | 合計コストと初期頻度の総和を混同 | コストは0から開始しマージのたびに加算 |
次のステップ
- 発展: 実際のハフマン木を構築し各シンボルの符号語（0/1列）を復元
- 発展: 符号長に上限Lを課すLength-Limited Huffman Coding（Package-Merge法）
- 次回予告: 区間篩（Segmented Sieve・大区間の素数カウント）
自己評価
理解度: / /
自分の回答:
気づき・メモ: