Google Code Jam 2008 Round 1A : B. Milkshakes

続いて２問目。さすがに１問目より難しい。
http://code.google.com/codejam/contest/32016/dashboard#s=p1

N種類のミルクがあって、それぞれ麦芽入り・麦芽なしの２通りがある。
M人の人のミルクの好みを満たすように麦芽入り・麦芽なしを選択する。
麦芽入りミルクの量を最少にしたい。

最初、各人の好みは制限がないと思っていたので、DFSで解いたらLargeが通らなかった。
問題をよく見たら、麦芽入りの好みは各人最大１つまでらしい。
実際、麦芽入り数に制限がないとNP完全らしい。

結局Analysisに従って解いてみた。
全ミルク麦芽なしで開始し、各人の好みを満たしていく。

今のミルクの状態で好みを満たせない場合、麦芽入りが好きならそれを麦芽入りにする。
麦芽入りが好きじゃない場合は、条件を満たせないので終了。
１個麦芽入りを増やすと、逆に好みを満たせない人が出る場合があるので、再度１からチェックする。
計算量としてはO(N^2M)だけど、各人の条件の合計値TはMと同じなので、結局O(N^2)で行ける。

int N,M,NM;
int T[3001],S[3001],NT,pat[3001];
int rm;
int resm[3000];


void solve(int _loop) {
	int i,j,k,resa,resb;
	int a,b,c,d;
	
	GET2(&N,&M);
	NT=0;
	FOR(i,M) {
		T[i]=GETi();
		S[i]=NT;
		FOR(j,T[i]) {
			pat[NT]=GETi();
			if(GETi()==0) pat[NT]*=-1;
			NT++;
		}
	}
	
	ZERO(resm);
	
	//先に1個しか好みが無いのを処理してしまう
	NM=0;
	FOR(i,M) {
		if(T[i]==1 && pat[S[i]]>0) {
			resm[abs(pat[S[i]])]=1;
		}
		else {
			T[NM]=T[i];
			S[NM]=S[i];
			NM++;
		}
	}
	
	i=0;
	M=NM;
	while(i<M) {
		//現状で満足しているか？
		int ok=0;
		int mi=-1;
		FOR(j,T[i]) {
			int type=abs(pat[S[i]+j]);
			int mel=(pat[S[i]+j]>0)?1:0;
			if(mel==1) mi=j;
			if(resm[type]==mel){ ok=1; break;}
		}
		
		if(ok) {
			i++;
		}
		else {
			if(mi==-1) {
				//1にできるものがもうないのでアウト
				_PE("Case #%d: IMPOSSIBLE\n",_loop);
				return;
			}
			//1を１個追加
			resm[abs(pat[S[i]+mi])]=1;
			i=0;
		}
	}
	
	_PE("Case #%d:",_loop);
	FOR(i,N){ _PE(" %d",(resm[i+1]<1)?0:1);}
	_PE("\n");
}

まとめ

実装は単純だけど、最初アルゴリズムを思いつくまでが大変そうだ。