Namaran

Code daily. Without assist.

2026-09-03

histogram.cpp

std::vector<int> histogram(const std::vector<int>& xs, int k) {
}

xs に 0 から k - 1 までの各値が何回現れるかを数える histogram を書いてください。返すのは長さ k の std::vector<int> で、添字 i の要素が値 i の出現回数です。この範囲の外の値は数えません。k は 0 以上で、0 のときは空の vector を返します。

入力例 1

histogram({1, 0, 1, 3}, 3)

出力例 1

{1, 2, 0}

入力例 2

histogram({2, 2, -1}, 4)

出力例 2

{0, 0, 2, 0}

入力例 3

histogram({5}, 0)

出力例 3

{}
Reference
std::vector<int> histogram(const std::vector<int>& xs, int k) {
    std::vector<int> h(k);
    for (int x : xs)
        if (0 <= x && x < k)
            ++h[x];
    return h;
}

回数を添字の位置で数えるので、先に k 個の要素を 0 で用意します。std::vector<int> h(k) は要素数 k の vector を作って各要素を値初期化するので、int の要素はすべて 0 から始まります。

ここを h.reserve(k) にすると、容量は確保されても要素数は 0 のままです。h[x] は要素のない位置を指すので、書き込んだ時点で未定義動作です。push_back で後ろに積むなら reserve、添字で書くなら要素数を決める h(k) か resize(k)、と使い分けます。

0 <= x && x < k の確認には2つの役目があります。範囲の外の値を数えないことと、h[x] が要素の外を指さないことです。負の x を添字に使うと std::size_t に変換されて巨大な値になるので、下限も確かめます。

掲載したのは参考実装で、唯一の正解ではありません。値ごとに std::ranges::count を呼んでも同じ結果になりますが、xs を k 回走査することになります。