kmjp's blog

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

Rockethon 2015 : D2. Constrained Tree

D問題は苦戦したけど何とか自力で解けた。
http://codeforces.com/contest/513/problem/D2

問題

DFSでpre-order順に1~Nの番号をふった根付バイナリツリーを考える。
ここでC個の情報が与えられる。
各情報では「A[i]番頂点の左or右のサブツリーにB[i]番の頂点が含まれる」という条件が示される。

条件を満たす根付バイナリツリーが存在するなら、それを構築し、in-order順で頂点番号を出力せよ。

解法

F(L,R,MaxR)という再帰関数を考え、F(1,N,N)から初めて再帰的に処理を行っていく。

  • L: 現在の頂点番号
  • R: Lを頂点としたサブツリーに含まなければならない頂点番号の最大値
  • MaxR: Lを頂点としたサブツリーに含んでもよい最大値

F(L,R,MaxR)はLを根とするサブツリーを作った上、そこに含まれる最大の頂点番号Xを返すものとする。
(当然R≦X≦MaxRでなければならない)

頂点Lに対しA[i]=Lとなる条件が存在するとする。
その場合、Lの左側の子になる頂点条件がいくつかある場合、Lの左側の子にはそのような条件のうち最大値MaxLまでを含まなければならない。
F(L+1,MaxL,MaxR)を再帰的に処理したとき、その値をXlとする。
MaxL≦Xl≦MaxRでない場合、条件を満たす木は作れない。

その後Lを出力し、Lの右側のサブツリーとしてF(Xl+1,R,MaxR)を処理して返り値をF(L,R,MaxR)の返り値として返せばよい。

int N,C;
vector<int> E[1010000][2];
stringstream S;

int dfs(int L,int R,int MR) {
	if(L>R) return R;
	
	sort(E[L][0].begin(),E[L][0].end());
	sort(E[L][1].begin(),E[L][1].end());
	int LMa=E[L][0].empty()?-1:E[L][0].back();
	int RMi=E[L][1].empty()?MR+1:E[L][1][0];
	int RMa=E[L][1].empty()?-1:E[L][1].back();
	
	if(LMa>MR || RMa>MR) _P("IMPOSSIBLE\n"), exit(0);
	
	int ret=max(L,dfs(L+1,LMa,MR));
	if(ret>=RMi) _P("IMPOSSIBLE\n"), exit(0);
	S << L+1 << " ";
	return max(ret,dfs(ret+1,max(R,RMa),MR));
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>C;
	FOR(i,C) {
		cin>>x>>y>>s;
		if(x>=y) return _P("IMPOSSIBLE\n");
		E[x-1][s[0]=='R'].push_back(y-1);
	}
	dfs(0,N-1,N-1);
	cout<<S.str()<<endl;
}

まとめ

CFは10^6回再帰してもスタック問題ないのね。