2026-11-13
cost.cpp
#include <iostream>
#include <set>
int main() {
std::set<int> q{1, 2, 3, 4};
int total = 0;
while (q.size() > 1) {
int a = q.extract(q.begin()).value();
int b = q.extract(q.begin()).value();
total += a + b;
q.insert(a + b);
}
std::cout << total << '\n';
}
出現回数が 1, 2, 3, 4 回の4文字を、出現回数に応じた長さの 0 と 1 の符号にしたとき、全体が何ビットになるかを求めるプログラムです。回数の小さい2つを取り出し、その和を足し込んでから戻す操作を、値が1つになるまで繰り返します。本来は 19 を出力するはずが、いまは 10 を出力します。
Answer
Wrong
std::set<int> q{1, 2, 3, 4};
入力の 1, 2, 3, 4 に重複は無いので、std::set でも困らないように見えます。重複が生まれるのは、ループが戻す和のほうです。1回目は 1 と 2 を取り出して total を3にし、和の3を insert します。ところが q にはもとの3がまだ残っていて、std::set は同じ値を2つ持てないので、この insert は何もしません。q は {3, 4} になり、2回目は 3 + 4 = 7 を足して total が10、q は {7} になってループが終わります。3が1つ消えた分、操作が1回少なくなり、足し込む和も変わりました。
Right
std::multiset<int> q{1, 2, 3, 4};
std::multiset は同じ値をいくつでも持てるので、戻した3はもとの3と並んで残ります。{3, 3, 4} から 3 + 3 = 6、{4, 6} から 4 + 6 = 10 を足し、total は 3 + 6 + 10 = 19 になります。extract と insert は std::multiset にもあり、ほかの行はそのまま使えます。入力そのものに同じ回数の文字が並ぶ場合も、すべての値が残ります。1
- 小さい順に取り出すだけなら、
std::priority_queue<int, std::vector<int>, std::greater<>>も同じ値をいくつでも持てます。この用途でよく使われるのはこちらで、topとpopの2行で1つを取り出します。