TopCoder SRM 525 Div1 Medium Rumor

問題

n匹のうさぎがいる。
2種類のうわさをうさぎ全体に広げたい。
最初、knowledgeで指定されるうさぎが、2種類のうわさを両方知っている。


各うさぎは、

  • 1日に、1種類のうわさを何匹にでも広めることができる
  • 1日に何種類のうわさでも聞くことができる。

どのうさぎからどのうさぎへうわさが伝わるかは有向グラフによってあたえられる。


2種類のうわさが全てのうさぎに伝わるまでの最短日数を求めよ。
不可能な場合は-1を出力せよ。

制約条件

うさぎの数≦16

方針

それぞれのうさぎについて、
2種類のうわさを伝え終えた後は何もしなくていい。
ということは、2種類のうわさを同時に知った場合、どちらを先に伝えるかを2^16通り決めてうわさが伝わるまでの日数を求めればいい。

ソースコード

int n;
bool e[20][20];

class Rumor {
	public:
	int getMinimum(string knowledge, vector <string> graph) 
	{
		n=graph.size();
		memset(e,0,sizeof(e));
		rep(i,n)rep(j,n)e[i][j]=graph[i][j]=='Y';
		
		ll flag=0;
		rep(i,n)if(knowledge[i]=='Y')flag|=3ll<<2*i;
		int ans=inf;
		rep(mask,1<<n){
			bool used[32]={};
			int turn=0;
			ll cur=flag;
			
			for(;;turn++){
				if(cur==(1ll<<2*n)-1){
					ans=min(ans,turn); break;
				}
				ll next=cur;
				rep(i,n)if(cur>>2*i&3){
					int rumor=mask>>i&1;
					if((cur>>2*i+rumor&1)==0||(cur>>2*i+1-rumor&1)&&used[2*i+rumor])rumor=1-rumor;
					used[2*i+rumor]=1;
					rep(j,n)if(e[i][j])next|=1ll<<2*j+rumor;
				}
				if(cur==next)break;
				cur=next;
			}
		}
		return ans==inf?-1:ans;
	}
};

別解

全探索(幅優先探索
状態数はあまり多くないので、
うわさが全部のうさぎにつたわった瞬間に探索を打ち切るようにすれば間に合う。


全てのうさぎにうわさが伝わらない場合は、前処理によってはじく。

ソースコード

最悪ケースで150msくらい。

int n;
bool g[20][20],e[20][20];
ll old;
int turn;
ll q[1<<21]; int qt[1<<21];
int h,t;
ll used[1<<22];
void push(ll v){
	ll hash=(v+12345)*6789%3999971;
	for(;used[hash]!=~0;hash=hash==3999970?0:hash+1);
	used[hash]=v;
}
bool contain(ll v){
	ll hash=(v+12345)*6789%3999971;
	for(;used[hash]!=~0;hash=hash==3999970?0:hash+1)
	if(used[hash]==v)return 1;
	return 0;
}
bool finish;
void rec(ll flag,int cur){
	if(finish)return;
	if(cur==n){
		if(!contain(flag)){
			q[t]=flag; qt[t++]=turn;
			if(flag==(1ll<<2*n)-1)finish=1;
			push(flag);
		}
		return;
	}
	if(old>>2*cur&1){
		ll next=flag;
		rep(i,n)if(e[cur][i])next|=1ll<<2*i;
		if(next!=flag)rec(next,cur+1);
	}
	if(finish)return;
	if(old>>2*cur&2){
		ll next=flag;
		rep(i,n)if(e[cur][i])next|=2ll<<2*i;
		if(next!=flag)rec(next,cur+1);
	}
	if(finish)return;
	rec(flag,cur+1);
}

class Rumor {
	public:
	int getMinimum(string knowledge, vector <string> graph) 
	{
		n=graph.size();
		memset(e,0,sizeof(e));
		rep(i,n)rep(j,n)g[i][j]=e[i][j]=graph[i][j]=='Y';
		rep(i,n)g[i][i]=1;
		
		rep(k,n)rep(i,n)rep(j,n)g[i][j]|=g[i][k]&&g[k][j];
		rep(i,n){
			bool ok=0;
			rep(j,n)if(knowledge[j]=='Y'&&g[j][i])ok=1;
			if(!ok)return -1;
		}
		
		
		ll flag=0;
		rep(i,n)if(knowledge[i]=='Y')flag|=3ll<<2*i;
		h=t=0;
		memset(used,~0,sizeof(used));
		push(flag);
		q[t]=flag; qt[t++]=0;
		finish=0;
		while(h<t){
			flag=q[h];
			turn=qt[h++];
			if(flag==(1ll<<2*n)-1)return turn;
			turn++;
			old=flag;
			if(turn<n+2)rec(flag,0);
		}
		return -1;
	}
};