b418. 八成真物

Problem

「偽物比真物更有價值」—貝木泥舟
「真物和偽物一樣有價值」—忍野咩咩
「偽娘比真娘更有價值」—精英島民

任兩個物品的相似度 $sim(A, B) = frac{|A cap B|}{|A cup B|}$，換句話說把 $A$ 具有的特徵和 $B$ 具有的特徵類型取交集、聯集個數，相除就能得到其相似度。例如有 5 個特徵，若 A 表示成 11001、B 表示成 01100，$sim(A, B) = frac{|{2}|}{|{1, 2, 3, 5}|} = 0.25$。

現在盤面上有 N 個物品、M 種特徵，請問相似度大於等於 0.8 的相似對數 $S$ 有多少種。為了讓這一題更有趣味，算法允許偽物，輸出 $frac{S}{N(N-1)/2} times 100$。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

8 10
0111101101
0111101100
0111101100
0111101101
1100101010
0111101100
0111101100
0011101111
  
8 10
1111101100
1011101100
1010101100
1010111010
0100110100
1011101100
1110110000
1011111100

Sample Output

1
2

53.57
25.00

Solution

利用 std::bitset 加速交集和聯集運算，將數個屬性壓縮到一個 32-bits 單位，然後藉 bitcount 盡可能在 $O(1)$ 的時間內完成，就有機會通過這一題。一般的 $O(N^2 M)$ 比 $O(N^2 M/32)$ 慢個五六倍。

此外，特別小心浮點數計算誤差，5.0/4.0 >= 0.8 == false，用乘法判定大於閥值的操作。

關於 LSH 的部分，還在進行測試，若 signature 計算太慢，還不如直接暴力法，若能分散找到 signature 或者是預先有辦法處理好，那分桶計算就會好一點。

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

#include <bits/stdc++.h> 
using namespace std;
int main() {
	int n, m;
	char s[1024];
	while (scanf("%d %d", &n, &m) == 2) {
		bitset<512> attr[n];
		for (int i = 0; i < n; i++) {
			scanf("%s", s);
			attr[i] = bitset<512>(s);
		}
		
		double ret = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i+1; j < n; j++) {
				int a = (attr[i]&attr[j]).count();
				int b = (attr[i]|attr[j]).count();
				if (5 * a >= 4 * b)
					ret++;
			}
		}
		printf("%.2lfn", ret * 100 / (n * (n-1)/2));
	}
	return 0;
}