kmjp's blog

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

Codeforces ECR #190 : F. Game on Growing Tree

これは解けても良かったな。
https://codeforces.com/contest/2230/problem/F

問題

木を成す無向グラフを使った2人ターン制のゲームを考える。

初期状態で全点は白い。
先手は、初回は任意の場所にコマを置きその点を赤く塗る。以降は、隣接する白マスのうち1つを選びコマを移動してその点を青く塗る。
後手は、任意の白マスを青く塗る。
先手は赤マスを最大化、後手は最小化するとき、赤マスは何マスになるか。


木に徐々に点を追加していくクエリが与えられるので、そのつど上記ゲームの解を答えよ。

解法

クエリは置いておいて、まず1つの木における解を考える。
先手がSubTreeのうちどこに行こうとするかを考えると、後手は赤マスが最大となる子頂点をつぶしに来るので、先手は2番目に赤マスが増える子頂点を選ぶ。
よって、各点から子頂点に遷移したときに得られる赤マスの最大値3個まで持って、全方位木DPすればよい。

また、この問題の解はクエリに対し単調増加で、かつ高々O(log(頂点数))程度の値になる。
よって二分探索の要領で、同じ解になる範囲を求めることで、全方位木DPの回数を削減できる。

int Q;
vector<int> E[202020];
int ret[202020];

int dp1[202020],dp2[202020],dp3[202020];
int M;

int dfs2(int cur,int pre) {
	vector<int> cand={1,1,1};
	FORR(e,E[cur]) if(e!=pre&&e<M) cand.push_back(dfs2(e,cur)+1);
	sort(ALL(cand));
	reverse(ALL(cand));
	dp1[cur]=cand[0];
	dp2[cur]=cand[1];
	dp3[cur]=cand[2];
	return dp2[cur];
}

void dfs3(int cur,int pre,int pv) {
	int cand[]={dp1[cur],dp2[cur],dp3[cur],pv+1};
	sort(cand,cand+4);
	reverse(cand,cand+4);
	dp2[cur]=cand[1];
	FORR(e,E[cur]) if(e!=pre&&e<M) {
		if(dp2[e]+1==cand[0]||dp2[e]+1==cand[1]) dfs3(e,cur,cand[2]);
		else dfs3(e,cur,cand[1]);
	}
}

int hoge(int M_) {
	M=M_;
	
	dfs2(0,-1);
	dfs3(0,-1,0);
	
	
	int ma=0;
	int i;
	FOR(i,M) ma=max(ma,dp2[i]);
	return ma;
}



void dfs(int L,int R,int retL,int retR) {
	if(L>=R) return;
	if(retL==retR) {
		while(L<R) ret[L++]=retL;
		return;
	}
	int M=(L+R)/2;
	
	ret[M]=hoge(M);
	dfs(L,M,retL,ret[M]);
	dfs(M+1,R,ret[M],retR);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	FOR(i,Q) {
		cin>>x;
		E[x-1].push_back(i+1);
		E[i+1].push_back(x-1);
	}
	dfs(2,Q+2,1,17);
	
	FOR(i,Q) cout<<ret[i+2]<<" ";
	cout<<endl;
	
	
}

まとめ

6問回のボス問にしては複雑でない。