Contents
ベル数とは？
わかりにくいタイトルで申し訳ありませんが、ここではN個のものをグループに分ける方法（グループの順番、グループ内の順番は区別しない）を考えます。この個数をベル数 B(N) といいます。3つのものをグループにわける方法は {a, b, c}, {a}, {b, c}, {b}, {a, c}, {c}, {a, b}, {a}, {b}, {c}の5とおりがあるので B(3) = 5 です。
全列挙する方法はいくつかありますが、再帰（要素を既存のそれぞれのグループに所属させる。ただし新しい要素のみが所属するグループも作る）を用いて行うことができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
static List<int[]> Bell(int n) { List<int[]> rets = new List<int[]>(); int[] temp = new int[n]; F(0, 0); return rets; void F(int idx, int max) { if (idx == n) { rets.Add((int[])temp.Clone()); return; } for (int i = 0; i <= max; i++) { temp[idx] = i; if (max <= i) F(idx + 1, max + 1); else F(idx + 1, max); } } } |
Bell(3)だと {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {0, 1, 1}, {0, 1, 2} のように3つの要素が 0～2 のどのグループに属するのかを示す配列のリストが返されます。
使ってみる
問題の趣旨
「袋 1, 袋 2, …, 袋 N をいくつかのグループに分け、グループごとにその袋に入った石の数を合計し、その合計の排他的論理和をとった値」としてあり得るものの個数を求めよ。
さきほど定義したBellメソッドを使って以下のようなコードを書いてみます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); HashSet<long> set = new HashSet<long>(); List<int[]> groups = Bell(N); foreach (var group in groups) { long[] sums = new long[N]; for (int i = 0; i < N; i++) { int num = group[i]; sums[num] += A[i]; } long xor = 0; foreach (var v in sums) xor ^= v; set.Add(xor); } Console.WriteLine(set.Count); } } |
これで良さそうなのですが、なぜか通らないテストケースがあります。
ハッシュが衝突している？
HashSet<T>.Add()の計算量は通常 O(1) なのですが、そうでない場合があります。HashSet<T>の内部データ構造はハッシュテーブルなのですが、ハッシュが衝突してしまう場合は O(N) に近づいていきます。この場合はlong型なのでハッシュが衝突しやすくなっているようです。
ハッシュの衝突を減らすためにHashSetを複数（ここでは32個）つくります。そして下位5ビットで格納場所を変えます。また格納するときは右に5ビットシフトさせます。これでハッシュの衝突を減らすことができるのですべてのテストケースを通すことができるようになりました。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); HashSet<long>[] sets = new HashSet<long>[1 << 5]; for (int i = 0; i < (1 << 5); i++) sets[i] = new HashSet<long>(); List<int[]> groups = Bell(N); foreach (var group in groups) { long[] sums = new long[N]; for (int i = 0; i < N; i++) { int num = group[i]; sums[num] += A[i]; } long xor = 0; foreach (var v in sums) xor ^= v; sets[xor & ((1 << 5) - 1)].Add(xor >> 5); } Console.WriteLine(sets.Sum(_ => _.Count)); } } |
