Namaran

Code daily. Without assist.

2026-10-27

same_counts.c

struct entry {
    int key, count;
};

struct table {
    struct entry slots[16];
};

const struct entry* find(const struct table* t, int key);

bool same_counts(const struct table* a, const struct table* b) {
}

struct table は、キーごとの個数を持つハッシュ表です。キー k は枠 k % 16 に置き、埋まっていれば次の枠へ順に進んで空きに置きます。count が 0 の枠は空きです。find は t からキー key の枠を探して返し、無ければ nullptr を返します。2つの表 a と b が、同じキーの集まりを、キーごとに同じ個数で持つときに true を返す same_counts を書いてください。どちらも空の表なら true です。例では、表に入れたキーと個数を、入れた順に {キー: 個数} で書きます。

入力例 1

a = {3: 2, 19: 1}, b = {19: 1, 3: 2}

出力例 1

true

入力例 2

a = {3: 2}, b = {3: 2, 5: 1}

出力例 2

false

入力例 3

a = {}, b = {}

出力例 3

true
Reference
bool same_counts(const struct table* a, const struct table* b) {
    int n = 0;
    for (int i = 0; i < 16; i++) {
        const struct entry* e = &a->slots[i];
        if (e->count == 0)
            continue;
        const struct entry* f = find(b, e->key);
        if (f == nullptr || f->count != e->count)
            return false;
        n++;
    }
    for (int i = 0; i < 16; i++)
        if (b->slots[i].count != 0)
            n--;
    return n == 0;
}

16個の枠を a と b で1つずつ見比べる書き方は使えません。入力例1の2つの表は中身が同じですが、3 と 19 はどちらも枠3を指すので、先に入れたほうが枠3に、後から入れたほうが枠4に入ります。同じ中身でも、入れた順によって枠の並びが変わります。

そこで a の空きでない枠を順に見て、そのキーを find で b から探し、無いか個数が違えば false を返します。ただし、これだけでは b にしか無いキーを見落とします。入力例2では a の 3 が b にも同じ個数で入っているので、a の側から確かめるだけだと true になってしまいます。a のキーがすべて b にあり、さらにキーの数が同じなら、b に余分なキーは残りません。参考実装は a で数えた数から b の空きでない枠の数を引き、0 になるかで確かめています。

掲載したのは参考実装で、唯一の正解ではありません。b の側からも find で a を引き、両方向に確かめる書き方もあります。