Codeforces #782 : Div2 F. Tree and Permutation Game

またややこしい問題設定。
https://codeforces.com/contest/1659/problem/F

問題

N頂点の木を成す無向グラフと、1～Nの順列Pを使った2人制ゲームを考える。
初期状態でトークンが頂点Xにおいてある。

以下の手順でゲームを進める。

• 先手は、2つの値u,vを定め、P中のuとvの位置を入れ替える。ただし、uまたはvにトークンがある場合はこれを行えない。
• その後、後手はトークンを隣接する頂点に動かさなければならない。

先手はPをソートしたくて、後手はさせたくない。
両者最適手を取るとき、勝者はどちらか。

解法

• 直径が3以上の場合、先手必勝である。
• 元々ソート済み、または初手でソート可能なら先手が勝つ。
• あとは、直径が2なので、中心とトークンの初期位置と不揃いな頂点数で決まる。

int T,N,X;
vector<int> E[202020];
int P[202020];

pair<int,int> farthest(int cur,int pre,int d,vector<int>& D) {
	D[cur]=d;
	pair<int,int> r={d,cur};
	FORR(e,E[cur]) if(e!=pre) r=max(r, farthest(e,cur,d+1,D));
	return r;
}

pair<int,vector<int>> diameter() { // diameter,center
	vector<int> D[2];
	D[0].resize(N);
	D[1].resize(N);
	auto v1=farthest(0,0,0,D[0]);
	auto v2=farthest(v1.second,v1.second,0,D[0]);
	v1=farthest(v2.second,v2.second,0,D[1]);
	pair<int,vector<int>> R;
	R.first = v2.first;

	return R;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>X;
		X--;
		FOR(i,N) E[i].clear();
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		FOR(i,N) {
			cin>>P[i];
			P[i]--;
		}
		if(diameter().first>=3) {
			cout<<"Alice"<<endl;
			continue;
		}
		vector<int> inval;
		FOR(i,N) if(i!=P[i]) inval.push_back(i);
		if(inval.empty()) {
			cout<<"Alice"<<endl;
			continue;
		}
		if(inval.size()==2&&inval[0]!=X&&inval[1]!=X) {
			cout<<"Alice"<<endl;
			continue;
		}
		
		vector<int> vis(N);
		int sw=0,center;
		FOR(i,N) {
			if(E[i].size()>=2) center=i;
			if(vis[i]==0) {
				sw--;
				x=i;
				while(vis[x]==0) {
					vis[x]++;
					sw++;
					x=P[x];
				}
			}
		}
		
		int parity=(sw+(center!=X))%2;
		if(center==P[center]) {
			cout<<(parity?"Alice":"Bob")<<endl;
		}
		else if(X==center&&center!=P[center]) {
			cout<<"Bob"<<endl;
		}
		else if(P[center]==X) {
			cout<<"Bob"<<endl;
		}
		else {
			cout<<(parity?"Alice":"Bob")<<endl;
		}
		
	}
}

まとめ

この場合分けを正確にコンテスト中にやり切れる気はしないなぁ。