2026-11-13
merge.cpp
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
int main() {
std::priority_queue q{std::greater<>{}, std::vector<int>(48, 1)};
int total = 0;
while (q.size() > 1) {
int a = q.top();
q.pop();
int b = q.top();
q.pop();
total += a + b;
q.push(a + b);
}
std::cout << total << '\n';
}
これは何を出力するでしょうか?
Answer
Output
272
std::greater<> を渡した priority_queue は、top() がいちばん小さい値を返します。ループは小さい2つを取り出し、その和を total に足してキューに戻すことを、要素が1つになるまで47回繰り返します。47回を1回ずつ追う代わりに、足される和が何を数えているかを見ます。キューの値はどれも、最初の1を何個か束ねたもので、値はその個数です。和 a + b を足すことは、新しくできた束に含まれる1を1個ずつ数えることなので、total は「1つ1つの1が、自分を含む束が作られた回数」を48個分足したものになります。
この回数は段ごとに数えられます。キューに1が残っている間は1どうしが組になり、戻した2は1より大きいので、1を使い切るまで取り出されません。48個の1は24個の2になり、続いて12個の4、6個の8、3個の16になります。どの段でも48個の1がそれぞれ1回ずつ束に入るので、4段で 48 × 4 = 192 です。残った3個の16は、16 + 16 = 32 を作ってから、16 + 32 = 48 を作ります。ここで足されるのは 32 + 48 = 80 で、合計は 192 + 80 = 272 です。1の側から数えると、先に組にならなかった16個は5回、32を作った32個は6回束に入り、16 × 5 + 32 × 6 = 272 になります。
48個の1を、2の累乗の個数のように同じ深さまで均等に束ねられると考えると、全員が6回で 288、あるいは全員が5回で 240 と答えてしまいます。48は2の累乗ではないので、最後の3個の16で回数に差が出ます。このループは Huffman 符号を作る手順そのもので、1つ1つの1が束に入った回数はその記号の符号の長さ、total は全記号を符号にしたときのビット数の合計です。1
- Huffman 符号は、出現回数の少ない2つを繰り返しまとめて木を作り、根からの深さを符号の長さにする方法です。出現回数がすべて等しい48記号なら、16記号に5ビット、32記号に6ビットの符号が割り当てられます。