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; }