CSAcademy Round #66 : E. Domino Train

なんか問題設定がややこしい。
https://csacademy.com/contest/round-66/task/domino-train/

問題

N個のドミノがある。
各ドミノは２つの数字が書かれたブロックで構成されており、順方向だと(A[i],B[i])、逆方向だと(B[i]、A[i])と並ぶ。

初期状態でN個のドミノ列がある。
各ドミノ列iはi番のドミノ1個で構成される。
この時、各ドミノの方向は任意に選択できる。

この状態で(N-1)個のクエリが与えられる。
各クエリではドミノ番号が1つ与えられるので、その番号のドミノを含むドミノ列と、他の任意のドミノ列を1つくっつける。
その際、個々のドミノ列の前後を反転することはできないが、どちらのドミノ列を前にするかは選択できる。

最終的にN個のドミノから含まれる1個のドミノ列が生成される。
この時、ドミノ列中で連続する2個のドミノについて、前のドミノの後ろ側の数字と、後ろ側のドミノの前の数字が一致した場合、マッチ数が1増加するとする。
最終的なマッチ数が最大となるよう、初期状態のドミノの方向と、クエリに対する連結方法を答えよ。

解法

この問題は前半パートと後半パートに分けられる。
前半は最終的なドミノ列を求めるパートで、後半は連結順を答えるものである。
と言っても後半は単純で、ドミノ列中の順番はわかっているので、各ドミノ番号に対し、自身が含まれるドミノ列を求めて前か後ろのドミノ列と連結すればよい。
これはset等で容易に行える。

あとは前半パートである。
ドミノ中の数字が頂点に相当するグラフを考える。
(A[i],B[i])のドミノがある場合、その2頂点間に辺を張る。

こうすると、この問題は以下のように書き換えられる。
全ての辺を1回ずつ通る最短パスを求めよ、ただし不可能なら最小回数の辺を追加してよい。
辺の追加は、マッチしないドミノの連結に相当する。

こうするとあとは容易で、各連結成分において、奇数次数の頂点間に辺を追加して奇数次数の頂点を2個以下にし、ハミルトンパスを求めていけばよい。

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;



int N;
int X[201010],Y[201010];
int O[201010];
map<pair<int,int>,set<int>> M;
int L[201010];
vector<int> cand[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);
	}
	
	vector<int> GetPath(vector<int> V) {
		vector<int> O;
		
		FORR(v,V) if(E[v].size()%2) O.push_back(v);
		for(int i=1;i+1<(int)O.size()-1;i+=2) {
			add_path(O[i],O[i+1]);
		}
		
		path.clear();
		if(O.empty()) dfs(V[0]);
		else dfs(O[0]);
		return path;
	}
};
UndirectedEulerPath<201000> uep;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i+1]>>Y[i+1];
		uep.add_path(X[i+1],Y[i+1]);
		uf(X[i+1],Y[i+1]);
		M[{X[i+1],Y[i+1]}].insert(i+1);
		M[{Y[i+1],X[i+1]}].insert(-(i+1));
	}
	
	vector<int> V;
	for(i=1;i<=100000;i++) cand[uf[i]].push_back(i);
	for(k=1;k<=100000;k++) if(cand[k].size()) {
		if(cand[k].size()==1 && uep.E[k].empty()) continue;
		vector<int> p=uep.GetPath(cand[k]);
		//FORR(pp,p) cout<<pp<<"/";
		//cout<<endl;
		FOR(i,p.size()-1) {
			x=p[i];
			y=p[i+1];
			
			if(M.count({x,y})==0) continue;
			if(M[{x,y}].empty()) continue;
			
			j=*M[{x,y}].begin();
			//cout<<j<<endl;
			if(j<0) {
				j=-j;
				swap(x,y);
				O[j]=1;
			}
			V.push_back(j);
			L[j]=V.size();
			M[{x,y}].erase(j);
			M[{y,x}].erase(-j);
		}
	}
	
	set<int> S;
	FOR(i,N+2) S.insert(i);
	//for(i=1;i<=N;i++) _P("!%d %d\n",i,L[i]);
	FOR(i,N-1) {
		cin>>x;
		x=L[x];
		auto nex=S.lower_bound(x+1);
		auto cur=nex;
		cur--;
		if(*nex==N+1) {
			nex--;
			cur--;
		}
		//_P("%d %d %d %d\n",V[*cur-1],V[*nex-1], *cur-1,*nex-1);
		_P("%d %d\n",V[*cur-1],V[*nex-1]);
		S.erase(nex);
	}
	FOR(i,N) _P("%d%c",O[i+1],(i==N-1)?'\n':' ');
	
}

まとめ

後半パート要るのかな…。