kmjp's blog

競技プログラミング参加記です

TopCoder SRM 650 Div1 Medium TheKingsRoadsDiv1、Div2 Hard TheKingsRoadsDiv2

SRM

本番どちらも正答率低めだったけど、幸い自分は割とすんなり解けた。
まぁ1WAしたのだけど。
http://community.topcoder.com/stat?c=problem_statement&pm=13271
http://community.topcoder.com/stat?c=problem_statement&pm=13667

問題

Hに対し、N=(2^H)-1頂点のグラフを考える。

Div1 Medium : N+2本の辺が与えられる。ここから3本の辺を抜いてバイナリツリーを作れるか。
Div2 Hard : N本の辺が与えられる。ここから1本の辺を抜いてバイナリツリーを作れるか。

解法

(2^H)-1頂点のバイナリツリーは、次数1の頂点が(2^(H-1))個、次数2の頂点が1、次数3の頂点が2^(H-1)-2頂点となる。

よってN-1本の辺がバイナリツリーを成すかどうかは、次数2の頂点を根として、子が0個または2個あり、子が2個ある場合は左右の頂点数が同じことをDFSで探索すればO(N)で検証できる。

Div2 Hardは抜く辺はN通りなので、抜く辺を総当たりして、それぞれバイナリツリー判定を行えばO(N^2)で解ける。

Div1 Mediumは辺の抜き方がO(N^3)なので愚直に行うと間に合わない。
そこで、まず2本まで総当たりで辺を除く。この段階で各次数の頂点数をチェックし「次数1の頂点が(2^(H-1))個、次数2の頂点が1、次数3の頂点が2^(H-1)-2頂点」からのずれが2以内だったら3辺目を総当たりし、またバイナリツリー判定を行えばよい。

２本の辺を除いた段階で大抵チェックではじかれるので、3辺目の探索はほとんど行われず、時間に間に合う。
実際、下記のコードでは１ケースのみ実行時間が1sを超えたが、他は0.1s以下である。

vector<int> E[1030];
int vis[1030];
int num[1040]={},N[15]={};

class TheKingsRoadsDiv1 {
	public:
	int H;
	
	bool ok(int cur,int pre,int num) {
		int i;
		bool ret=true;
		vis[cur]=1;
		if(num==0) return false;
		num--;
		
		if(E[cur].size()==1) return num==0;
		if(num%2) return false;
		if(pre!=-1 && E[cur].size()!=3) return false;
		
		FOR(i,E[cur].size()) if(E[cur][i]!=pre) ret &= ok(E[cur][i],cur,num/2);
		return ret;
		
	}
	
	string getAnswer(int h, vector <int> a, vector <int> b) {
		int i,x,j,L,X,Y,Z,H;
		
		H=(1<<h)-1;
		ZERO(num);
		ZERO(N);
		
		L=a.size();
		FOR(i,L) num[--a[i]]++, num[--b[i]]++;
		FOR(i,H) {
			if(num[i]>=10) return "Incorrect";
			N[num[i]]++;
		}
		
		FOR(X,L) {
			N[num[a[X]]]--;N[--num[a[X]]]++;
			N[num[b[X]]]--;N[--num[b[X]]]++;
			
			FOR(Y,X) {
				N[num[a[Y]]]--;N[--num[a[Y]]]++;
				N[num[b[Y]]]--;N[--num[b[Y]]]++;
				if(N[2]>3) goto out;
				if(N[1]>(1<<(h-1))+2 || N[1]<(1<<(h-1))-3) goto out;
				if(N[3]>(1<<(h-1)) || N[3]<(1<<(h-1))-4) goto out;
				FOR(Z,Y) {
					int st=-1;
					N[num[a[Z]]]--;N[--num[a[Z]]]++;
					N[num[b[Z]]]--;N[--num[b[Z]]]++;
					
					if(N[2]!=1) goto out2;
					if(N[1]!=(1<<(h-1))) goto out2;
					if(N[3]!=(1<<(h-1))-2) goto out2;
					
					FOR(x,1<<h) E[x].clear();
					FOR(j,L) if(j!=X && j!=Y && j!=Z) E[a[j]].push_back(b[j]),E[b[j]].push_back(a[j]);
					ZERO(vis);
					FOR(j,(1<<h)-1) if(E[j].size()==2) st=j;
					if(st!=-1 && ok(st,-1,(1<<h)-1) && count(vis,vis+(1<<h)-1,1)==(1<<h)-1) return "Correct";
					
					out2:
					N[num[a[Z]]]--;N[++num[a[Z]]]++;
					N[num[b[Z]]]--;N[++num[b[Z]]]++;
				}
				
				
				out:
				N[num[a[Y]]]--;N[++num[a[Y]]]++;
				N[num[b[Y]]]--;N[++num[b[Y]]]++;
			}
			N[num[a[X]]]--;N[++num[a[X]]]++;
			N[num[b[X]]]--;N[++num[b[X]]]++;
		}
		
		return "Incorrect";
	}
}

vector<int> E[1030];
int vis[1030];
class TheKingsRoadsDiv2 {
	public:
	int H;
	
	bool ok(int cur,int pre,int num) {
		int i;
		bool ret=true;
		vis[cur]=1;
		if(num==0) return false;
		num--;
		
		if(E[cur].size()==1) return num==0;
		if(num%2) return false;
		if(pre!=-1 && E[cur].size()!=3) return false;
		
		FOR(i,E[cur].size()) if(E[cur][i]!=pre) ret &= ok(E[cur][i],cur,num/2);
		return ret;
		
	}
	
	string getAnswer(int h, vector <int> a, vector <int> b) {
		int i,x,j;
		FOR(i,(1<<h)-1) {
			FOR(x,1<<h) E[x].clear();
			FOR(j,(1<<h)-1) if(i!=j) E[a[j]-1].push_back(b[j]-1),E[b[j]-1].push_back(a[j]-1);
			ZERO(vis);
			int st=-1;
			FOR(j,(1<<h)-1) if(E[j].size()==2) st=j;
			if(st!=-1 && ok(st,-1,(1<<h)-1) && count(vis,vis+(1<<h)-1,1)==(1<<h)-1) return "Correct";
		}
		return "Incorrect";
	}
}

まとめ

正答者は他の方法を取ってる人が多かった。
次数で絞り込んでる人も多少はいたけどね。