kmjp's blog

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

AtCoder ARC #095 : F - Permutation Tree

問題設定がややこしい。
https://beta.atcoder.jp/contests/arc095/tasks/arc095_d

問題

1~NのPermutationを成す数列Aに対し、以下のように木を成すグラフを作る。
1より大きいA[i]に対し、A[j]<A[i]となるjのうち最大のものを求め、iとjの間に辺を張る。

木を成すグラフが与えられる。
この木と同型のグラフを構築できるAのうち辞書順最小のものを求めよ。

解法

まずこのPermutationによるグラフの生成法だが、直径を成す頂点群のうち両端以外の頂点に何本か長さ1の分岐があるようなグラフを生成できる。
(解説によるとキャタピラグラフというらしい)

そこで、まず与えられる木がキャタピラグラフかを求めよう。
これはまず直径を求めた後、直径上にある頂点群が持つ辺の数を数えれば判定できる。
直径を成す頂点群において、直径以外の辺の数を順に並べてみる。
例えばテストケース1ならP=(0,0,2,0)である。(反転した方が辞書順最小なら反転する)

ここから直径の頂点i毎に端から以下のように数列を作っていこう。
未登場の頂点番号の最小値をXとする。Xの手前にP[i]個Xより大きな要素を置き、Xのあとに1個Xより大きい要素を置く。
例えばP[i]=2なら(X+1) (X+2) X (X+3)と置けばよい。あとはP[i+1]を処理するときは(X+4)から継続する。

int N;
vector<vector<int>> E;

pair<int,int> farthest(vector<vector<int>>& E, 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,e,cur,d+1,D));
	return r;
}

vector<pair<int,int>> diameter(vector<vector<int>>& E) { // diameter,center
	vector<int> D[2];
	D[0].resize(E.size());
	D[1].resize(E.size());
	auto v1=farthest(E,0,0,0,D[0]);
	auto v2=farthest(E,v1.second,v1.second,0,D[0]);
	farthest(E,v2.second,v2.second,0,D[1]);
	
	vector<pair<int,int>> R;
	//重心を取る場合
	for(int i=E.size()-1;i>=0;i--) if(D[0][i]+D[1][i]==v2.first) R.push_back({D[0][i],i});
	sort(ALL(R));

	return R;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	E.resize(N);
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	auto R=diameter(E);
	vector<int> A,B;
	int num=0;
	FOR(i,R.size()) {
		A.push_back(E[R[i].second].size());
		A.back()--;
		if(i>0 && i<R.size()-1) A.back()--;
		num+=1+A.back();
	}
	B=A;
	reverse(ALL(B));
	if(num!=N) return _P("-1\n");
	A=min(A,B);
	
	int nex=0;
	FOR(i,A.size()) {
		FOR(x,A[i]) cout<<nex+2+x<<" ";
		cout<<nex+1<<" ";
		nex+=1+A[i];
	}
	cout<<endl;
	
	
}

まとめ

キャタピラグラフになることに気づけば難しくない。