Namaran

Code daily. Without assist.

2026-10-24

k_smallest_test.cpp

bool is_k_smallest(std::vector<int> in, std::vector<int> out, std::size_t k) {
}

テストしたい関数は、整数の列 in から小さい方の k 個を取り出して返します。k が要素数以上なら全要素を返し、返す順序は問いません。この関数が返した out が正しい結果の1つなら true、そうでなければ false を返す判定 is_k_smallest を書いてください。in には同じ値が何度現れてもよく、in が空なら正しい結果は空の列だけです。

入力例 1

is_k_smallest({5, 1, 3, 1}, {1, 1}, 2)

出力例 1

true

入力例 2

is_k_smallest({5, 1, 3, 1}, {3, 1}, 2)

出力例 2

false

入力例 3

is_k_smallest({2, 1}, {1, 2}, 5)

出力例 3

true
Reference
bool is_k_smallest(std::vector<int> in, std::vector<int> out, std::size_t k) {
    k = std::min(k, in.size());
    std::ranges::sort(in);
    std::ranges::sort(out);
    return std::ranges::equal(out, std::span(in).first(k));
}

正しい out は1通りではありません。{5, 1, 3, 1} から2個なら {1, 1} でも並べ方は自由で、std::partial_sort のような1つの実装の出力と == で比べると、順序が違うだけの正しい結果を失敗にしてしまいます。取り出した値を順序のない集まりとして見れば、答えは1つに決まります。同じ値が何度現れてもよい集まりを多重集合(multiset)といい、in の小さい方の k 個がなす多重集合は、同じ値が並んでいても変わりません。

そこで両方を昇順に並べ替え、順序の自由を消してから比べます。並べ替えた in の先頭 k 個がその多重集合で、並べ替えた out がこれと要素ごとに一致すれば正しい結果です。std::ranges::equal は長さも比べるので、out の個数が足りない場合や多すぎる場合もここで false になります。k を in.size() で抑えておかないと、first(k) が範囲を超えて未定義動作になります。引数を値で受け取っているので、並べ替えても呼び出し側の列は変わりません。

もっともらしい書き方の多くは、条件のどれかを確かめ損ねます。out の各要素が in に含まれ、k 番目に小さい値以下であることだけを調べると、{5, 1, 3, 2} と k = 2 に対する {1, 1} のように、1つしかない値を2度返した誤りを通します。個数をそろえて値ごとに std::find で探す書き方も、重複を数えないので同じ誤りを見逃します。掲載したのは参考実装で、唯一の正解ではありません。並べ替えずに値ごとの出現回数を数えて比べる書き方もあります。