Codeforces 367(#215 Div1) D. Sereja and Sets

問題

集合A = {1, 2, 3, ..., n}をm個disjointに分割したA1, A2, ..., Amが与えられる。
Aiからk個を選び、それらの和集合Bを作る。


Bの要素を小さい順に並べた数列をb1, b2, ..., b|b|とする。
与えられた数dに対して、
b1≦d,
bi+1 - bi≦d(各iで)
n + d - 1≦b|b|
が成り立っている必要がある。


このようなBが選べるkの最小値を求めよ。

制約条件

n≦10^5
m≦20

方針

条件は、「b0 = 0, b|b|+1 = nとしたとき、隣り合うどの2数もdより離れていない」
と書くことができる。


したがって、長さdのある区間x, x+1, x+2, ..., x+d-1について、
xからx+d-1がそれぞれAiのどれに含まれるかをa(x), a(x+1), ..., a(x+d-1)と書くと、
{a(x), a(x+1), ..., a(x+d-1)}の全てが含まれないようなBの選び方をすると、
どうやってもこの部分でdより大きなギャップができるということになる。


C = {a(x), a(x+1), ..., a(x+d-1)}の全てが含まれないようなBの選び方
というのをbitで表せば、{1, 2, ..., m} - Cなる集合の部分集合はどれもダメ。


これを全ての区間について求めれば、ダメな集合がわかる。
部分集合DPで、ダメな集合を部分集合に伝播させることをしていけば、
O(m2^m)の時間で全てのダメな集合がわかる。

ダメじゃない集合で、最もサイズが小さいものを求めればよい。


自分はよくわからない枝刈りをして通した。

ソースコード

int *buildRMQ(int *a, int n){
	int logn = 1;
	for (int k = 1; k < n; k *= 2) ++logn;
	int *r = new int[n * logn];
	int *b = r;
	copy(a, a+n, b);
	for (int k = 1; k < n; k *= 2){
		copy(b, b + n, b + n); b += n;
		rep(i, n - k) b[i] |= b[i+k];
	}
	return r;
}
inline int minimum(int x, int y, int *rmq, int n){
	int z = y - x, k;
	if(z <= 0) return rmq[x];
	__asm(
		"bsrl %1, %0\n\t"
		: "=r"(k) : "r"(z) :
	);
	return rmq[x + n * k] | rmq[y + n * k - (1 << k) + 1];
}

int n, m, d;
int a[100010], ng[(1 << 20) - 1];

int main(){
	scanf("%d%d%d", &n, &m, &d);
	rep(i, m){
		int k, t; scanf("%d", &k);
		rep(j, k){
			scanf("%d", &t);
			a[t] |= 1 << i;
		}
	}
	
	int ans = m;
	int *rmq = buildRMQ(a, n + 1);
	
	for(int i = d; i <= n; i++){
		
		int x = minimum(i - d + 1, i, rmq, n + 1);
		//cerr<<"i: "<<i<<" x: "<<x<<endl;
		ng[x] = 1;
	}
	vi v;
	rep(i, 1 << m){
		ng[i] += ng[i - 1 & i] * 2;
		ng[i] = min(ng[i], 2);
		if(ng[i] == 1) v.pb(i);
	}
	dbg(v.size());
	
	rep(i, 1 << m){
		int b = __builtin_popcount(i);
		if(b >= ans) continue;
		
		bool ok = 1;
		rep(j, v.size()) if((i & v[j]) == 0){
			ok = 0;
			break;
		}
		if(ok) ans = min(ans, b);
	}
	
	cout << ans << endl;
	
	return 0;
}

本当はこんな感じ

int n, m, d;
int a[100010], ng[(1 << 20) - 1];

int main(){
	scanf("%d%d%d", &n, &m, &d);
	rep(i, m){
		int k, t; scanf("%d", &k);
		rep(j, k){
			scanf("%d", &t);
			a[t] |= 1 << i;
		}
	}
	
	int ans = m;
	int *rmq = buildRMQ(a, n + 1);
	
	for(int i = d; i <= n; i++){
		
		int x = minimum(i - d + 1, i, rmq, n + 1);
		ng[(1 << m) - 1 - x] = 1;
	}
	for(int i = (1 << m) - 1; i >= 0; i--){
		if(!ng[i]) ans = min(ans, __builtin_popcount(i));
		else rep(j, m) if(i & 1 << j) ng[i ^ 1 << j] = 1; //伝播
	}
	cout << ans << endl;
	
	return 0;
}