Codeforces #554 Div2 E. Neko and Flashback

最近Codeforcesの記事が後回しになっていて2か月分もたまってしまった。
https://codeforces.com/contest/1152/problem/E

問題

N要素の整数列Aがあったとするとき、以下のように数列を定義する。

• 長さ(N-1)の数列Bは、B[i]=max(A[i+1],A[i])で定義される
• 長さ(N-1)の数列Cは、C[i]=min(A[i+1],A[i])で定義される

B,Cを、同じ順で並べ替え方をしたB',C'が与えられる。
そのようなB',C'を生成できる可能性のあるAを1つ構築せよ。

解法

あるB[i],C[i]の組がある場合、B[i]≧C[i]でなければならない。
そのとき、AにおいてB[i]とC[i]が隣接していることを意味する。

そこで、頂点にラベルとして整数を持ち、そこに(N-1)個の辺をもつ無向グラフを考えよう。
このグラフでは,B[i]とC[i]のラベルを持つ頂点間に辺を張るものとする。

こうすると、このグラフにおいてオイラーパスが構築できれば条件を満たす数列が作れることになる。
後は自己辺・多重辺の存在を考慮しつつオイラーパスを張ろう。

int N;
int B[101010],C[101010];

template<int MV> class UndirectedEulerPath {
public:
	vector<int> path;
	multiset<int> E[MV];
	void add_path(int x,int y) { E[x].insert(y); E[y].insert(x); }
	
	void dfs(int cur) {
		while(E[cur].size()) {
			int tar=*E[cur].begin();
			E[cur].erase(E[cur].begin());
			E[tar].erase(E[tar].find(cur));
			dfs(tar);
		}
		path.push_back(cur);
	}
	
	bool GetPath() { // 開始地点を探し、条件を満たすか判定
		int fo=-1,odd=0,i,np=0;
		FOR(i,MV) {
			np += E[i].size();
			if(E[i].size()%2) odd++, fo=(fo==-1)?i:fo;
		}
		if(odd!=0 && odd!=2) return false;
		dfs(odd?fo:0);
		reverse(path.begin(),path.end());
		return path.size()==np/2+1;
	}

	vector<int> GetPath(int root) { //開始位置が確定している場合
		dfs(root);
		reverse(path.begin(),path.end());
		return path;
	}
};

vector<int> ret;
vector<int> D;
UndirectedEulerPath<202020> uep;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) cin>>B[i];
	FOR(i,N-1) cin>>C[i];
	FOR(i,N-1) {
		if(B[i]>C[i]) return _P("-1\n");
		D.push_back(B[i]);
		D.push_back(C[i]);
	}
	sort(ALL(D));
	D.erase(unique(ALL(D)),D.end());
	FOR(i,N-1) {
		B[i]=lower_bound(ALL(D),B[i])-D.begin();
		C[i]=lower_bound(ALL(D),C[i])-D.begin();
		uep.add_path(B[i],C[i]);
	}
	
	if(!uep.GetPath()) return _P("-1\n");
	FORR(r,uep.path) cout<<D[r]<<" ";
	
}

まとめ

2か月もたつと当時どう解いたか忘れちゃうんだけど、復習としては却っていいかもしれない。