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 を引き、両方向に確かめる書き方もあります。