Codeforces ECR #155 : E. Interactive Game with Coloring

Eまでは割と順調だった。
https://codeforces.com/contest/1879/problem/E

問題

N点の根付き木が与えられる。
各辺を任意に彩色できるとき、以下の条件を満たす最小の色数で彩色せよ。

彩色した木で、以下のゲームを行う。
審判がどこかの点にランダムでコインを置く。
その後、コインを置いた点に、各色の辺が何本接続されるかが与えられる。
そこで1色指定すると、ランダムでそのいずれかの辺に沿ってコインを動かす。
これを繰り返し、最短の移動回数で根に到達したい。

解法

• 根付き木から葉までの距離が1なら、1色で良い。
• 深さの偶奇に応じて2色に塗ったとき、どちらの色が親方向の辺か一意に特定できるなら、2色にする。
• それ以外の場合は3色。点の深さを3で割った余りに応じて3色で塗れば、常に親方向の辺を特定できる。

int N;
int P[101],D[101];
vector<int> C[101];
int S[101];
set<int> cand;
int V[2];

void go1() {
	int i,x;
	cout<<1<<endl;
	for(i=1;i<N;i++) cout<<1<<" ";
	cout<<endl;
	cin>>i>>x;
	assert(i==0&&x==1);
	cout<<1<<endl;
	cin>>x;
	assert(x==1);
	exit(0);
	
}

void go2() {
	int i,x;
	cout<<2<<endl;
	for(i=1;i<N;i++) cout<<(((D[i]%2)^S[i])+1)<<" ";
	cout<<endl;
	while(1) {
		cin>>i;
		if(i==1) exit(0);
		int A,B;
		cin>>A>>B;
		if(A==1) cout<<1<<endl;
		else cout<<2<<endl;
	}
	exit(0);
}

void dfs(int cur) {
	cand.insert(cur);
	if(C[cur].size()==1) {
		V[D[cur]%2]++;
	}
	FORR(c,C[cur]) dfs(c);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1;i<N;i++) {
		cin>>P[i];
		P[i]--;
		D[i]=D[P[i]]+1;
		C[P[i]].push_back(i);
	}
	
	//1色で行けるか？
	for(i=1;i<N;i++) if(P[i]!=0) break;
	if(i==N) {
		go1();
	}
	//2色で行けるか？
	int ok=1;
	FORR(c,C[0]) {
		cand.clear();
		V[0]=V[1]=0;
		dfs(c);
		if(V[0]&&V[1]) ok=0;
		if(V[1]) FORR(a,cand) S[a]=1;
	}
	
	if(ok) {
		go2();
	}
	
	cout<<3<<endl;
	for(i=1;i<N;i++) cout<<(D[i]%3+1)<<" ";
	cout<<endl;
	while(1) {
		cin>>i;
		if(i==1) exit(0);
		int A,B,C;
		cin>>A>>B>>C;
		if(A==0&&B==1) cout<<2<<endl;
		else if(B==0&&C==1) cout<<3<<endl;
		else if(C==0&&A==1) cout<<1<<endl;
	}
	
}

まとめ

本番割とすんなり通せてたな。