Namaran

Code daily. Without assist.

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

  1. 小さい順に取り出すだけなら、std::priority_queue<int, std::vector<int>, std::greater<>> も同じ値をいくつでも持てます。この用途でよく使われるのはこちらで、top と pop の2行で1つを取り出します。