TopCoder SRM 525 Div1 Medium Rumor

SRM524では大苦戦と思ったら、こちらはあっさり。
http://community.topcoder.com/stat?c=problem_statement&pm=11664

問題

N人の人がおり、そのうち何人かは2種類の噂を知っており、残りはどちらの噂も知らない。
時間１を掛け、各人はどちらかの噂を友人に展開出来る。
友人関係は有向辺で与えられる。
全員が全部の噂を知るのにかかる最短時間を求めよ。

解法

N<=16とかなり小さめ。
「各人、知ってる噂をどちらから展開するか」をbitmaskで持って総当たりし、あとは噂の展開をシミュレートするだけ。
1回のシミュレートは普通に書くとO(N^3)だけど、友人関係を32bit intで表現すればO(N^2)に落とせる。
全体でO(2^N*N^2)なので余裕。

class Rumor {
	public:
	string K;
	vector<string> G;
	int spm[16];
	int N;
	
	int dodo(int mask) {
		int i,j,k,x,y;
		int sp1,sp2;
		int kn1,kn2,nkn1,nkn2;
		
		sp1=sp2=0;
		kn1=kn2=0;
		FOR(i,N) kn1|=(K[i]=='Y')<<i;
		FOR(i,N) kn2|=(K[i]=='Y')<<i;
		nkn1=kn1;
		nkn2=kn2;
		
		FOR(i,20) {
			if(nkn1==(1<<N)-1 && nkn2==(1<<N)-1) break;
			
			FOR(j,N) {
				int sp=0;
				if((sp1&(1<<j))==0 && (sp2&(1<<j))==0) {
					if(mask&(1<<j)) {
						if(kn2&(1<<j)) sp=2;
						else if(kn1&(1<<j)) sp=1;
					}
					else {
						if(kn1&(1<<j)) sp=1;
						else if(kn2&(1<<j)) sp=2;
					}
				}
				else if((sp1&(1<<j))==0 && (kn1&(1<<j))) sp=1;
				else if((sp2&(1<<j))==0 && (kn2&(1<<j))) sp=2;
				
				if(sp==1) nkn1 |= spm[j],sp1 |= 1<<j;
				if(sp==2) nkn2 |= spm[j],sp2 |= 1<<j;
			}
			kn1=nkn1;
			kn2=nkn2;
		}
		return i;
	}
	
	int getMinimum(string knowledge, vector <string> graph) {
		K=knowledge;
		G=graph;
		N=K.size();
		int mi=20;
		
		int i,j;
		ZERO(spm);
		FOR(i,N) FOR(j,N) spm[i] |= (graph[i][j]=='Y')<<j;
		for(int mask=0;mask<1<<N;mask++) mi=min(mi,dodo(mask));
		
		if(mi>=20) return -1;
		return mi;
	}
};

まとめ

Div1 Mediumも結構難易度差激しいな。