AtCoder ABC #165 : E - Rotation Matching

PAST1問とGCJ1問まだ残してるんだけど。
https://atcoder.jp/contests/abc165/tasks/abc165_e

問題

1～Nの番号が付いた人がM個のコートで2人対戦を行う。
まず、初期状態でM個のコートで2個ずつ1～Nのいずれかの番号を振る。
すると同じコートに番号のある2人が対戦する。

その後、各コートに振られた番号をインクリメントし(ただしN+1は1に戻す)、同様に対戦を行う。
この手順をN周しても、同じ組が2回以上対戦しないような初期の番号配置を答えよ。

解法

初期状態で、コートiに(x[i],y[i]) (x[i]＜y[i])と割り当てたとき、(y[i]-x[i])及び(N+x[i]-y[i])で計算できる2M個の値が互いに異なっていればよい。
Nが奇数の時は、(1-originで)x[i]=i、y[i]=N-iにしておけばよい。
Nが偶数のとき、(y[i]-x[i])＜(N+x[i]-y[i])ならx[i]=i、y[i]=N-iにして、そうでなければx[i]=i,y[i]=N-1-iにしておくとよい。

int N;
int A[201010];
vector<int> V;
int ret[201010];
vector<int> E[201010];

void dfs(int cur,int pre) {
	int pos=lower_bound(ALL(V),A[cur])-V.begin();
	int rev;
	if(pos==V.size()) {
		rev=-1;
		V.push_back(A[cur]);
	}
	else {
		rev=V[pos];
		V[pos]=A[cur];
	}
	ret[cur]=V.size();
	
	
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur);
	
	if(rev==-1) {
		V.pop_back();
	}
	else {
		V[pos]=rev;
	}
}

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

まとめ

サンプル2がヒントとしてだいぶ大きい気がする。