2026-10-28
count_diff.c
int count_diff(const unsigned a[], const unsigned b[], int node, int leaves) {
}
大きなデータを leaves 個の断片に分け、断片ごとのハッシュ値を葉にした木を配列に入れます。leaves は2の累乗で、葉は添字 leaves から 2 * leaves - 1 に並び、添字 i の節には子 2 * i と 2 * i + 1 の値から計算したハッシュ値が入ります。添字1が根で、添字0は使いません。同じ形の2つの木 a と b について、値の違う葉の個数を返す count_diff を書いてください。node には調べる部分木の根の添字を渡し、木全体なら1です。2つの木は別のマシンにあり、節を1つ見るたびに通信が要るので、値の等しい節より下は見ないでください。内容が違えばハッシュ値も必ず違うものとします。leaves が1なら、根がそのまま葉です。例では、配列を複合リテラルで書きます。
入力例 1
count_diff((unsigned[]){0, 5, 1, 2}, (unsigned[]){0, 8, 1, 5}, 1, 2)
出力例 1
1
入力例 2
count_diff((unsigned[]){0, 5, 1, 2}, (unsigned[]){0, 5, 1, 2}, 1, 2)
出力例 2
0
入力例 3
count_diff((unsigned[]){0, 7}, (unsigned[]){0, 9}, 1, 1)
出力例 3
1
Reference
int count_diff(const unsigned a[], const unsigned b[], int node, int leaves) {
if (a[node] == b[node]) {
return 0;
}
if (node >= leaves) {
return 1;
}
return count_diff(a, b, 2 * node, leaves) + count_diff(a, b, 2 * node + 1, leaves);
}
節の値が等しければ、その下の葉もすべて等しいので、0を返してそこで止めます。この比較を最初に置くと、通信が要るのは値の違う節とその子だけになります。入力例2では根の値が等しいので、根を1回比べただけで0が返ります。
値が違う節については、それが葉かどうかで扱いが分かれます。葉は添字 leaves 以上にあるので、node >= leaves なら違う葉を1個見つけたことになり、1を返します。葉でなければ2つの子について同じことを調べ、個数を足します。leaves が1の入力例3では、根の添字1が leaves 以上なので、根を葉として数えます。
葉の範囲 a[leaves] から a[2 * leaves - 1] を順に比べるループでも同じ個数が出ますが、それでは葉を全部見ることになり、値の等しい節より下を見ないという条件を満たしません。掲載したのは参考実装で、唯一の正解ではありません。再帰の代わりに、調べる節の添字をスタックに積むループでも書けます。