Codeforces #215 Div1. D. Sereja and Sets

本番は解ききれなかったけど、アプローチはあってた。
後は最後まで解ききる力をつければ…。
http://codeforces.com/contest/367/problem/D

問題

1～Nの数が、A[0]～A[M-1]のM個の集合に格納されている。
各数は１個の集合のみに格納されているとする。

A[i]の集合をいくつか集めてそこに含まれる数値を昇順に並べた数列をB[0]～B[k-1]とするとき、数Dに対して以下を満たすようにしたい。
B[0]<=D、B[i+1]-B[i]<=D、N+1-B[k-1]<=D
このようなBを作るのに必要な最少のA[i]の個数を求めよ。

解法

Bの条件を言い換えると、Bの前後に0やN+1をつけた数列を考えたとき、隣接要素の差がD以下であることといえる。
逆にいうと、1～N中の連続するD個の数がある場合、そのD個が属する集合のうち1つは選択しないと隣接要素がD+1以上になってしまう。

この事実から、連続するD個が属する集合群をすべて選ばない、という選択肢は不可ということがわかる。
M<=20と小さいことから、あとは1～N中の連続するD個を順にたどっていき、そのD個が属する集合をbitmaskで管理して、そのbitmaskを含む選択肢は不可、ということをDPで求めればよい。
残された選択可能な選択肢のbitmaskのうち、bit数が最小になるものを選択すればよい。

int N,M,D;
int se[100001];
int nu[21],ng[1<<21];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M>>D;
	FOR(i,M) {
		cin>>x;
		FOR(j,x) se[GETi()-1]=i;
	}
	
	FOR(i,N) {
		nu[se[i]]++;
		if(i>=D) nu[se[i-D]]--;
		if(i>=D-1) {
			x=0;
			FOR(j,M) if(nu[j]) x|=1<<j;
			ng[x]=1;
		}
	}
	
	int r=M;
	FOR(i,1<<M) {
		if(ng[i]) {
			FOR(j,M) if((i&(1<<j))==0) ng[i^(1<<j)]++;
		}
		else {
			r=min(r,M-__builtin_popcount(i));
		}
	}
	_P("%d\n",r);
}

まとめ

今回のCFはどれも答えが簡潔に書けていいな。
問題文もわかりやすい。
ほんと前回のDiv2はひどかった…。