Codeforces #680 Div1 D. Rectangular Polyline

なるほど…
http://codeforces.com/contest/1444/problem/D

問題

2次元座標上で、軸に平行な線分で構成された単純な多角形があったとする。
その横辺の長さの集合と、縦辺の長さの集合が与えられたとき、元の図形を再構築せよ。

解法

左下の点を原点とする。
そこから上に凸な部分と下に凸な部分に分けて考える。
右上の点で上に凸な部分と下に凸な部分が再び合流することを考えると、縦辺の集合と横辺の集合を、それぞれ総和が等しくなるようにほぼ同数の辺の2つの集合に分ける必要がある。
これはbitsetを使ったDPを復元することで力業で実現できる。

あとは、片方の縦辺・横辺の集合の組を、上に凸に、もう片方を下に凸になるよう縦横交互に組み合わせていこう。

int T;
int N,S;
int X[1001];
bitset<1<<18> HB[501];

vector<vector<int>> hoge() {
	vector<int> R[2];
	int i;
	cin>>N;
	FOR(i,N) cin>>X[i];
	if(N>500) return {};
	
	HB[0][0]=1;
	S=0;
	FOR(i,N) {
		S+=X[i];
		HB[i+1]=HB[i] | (HB[i]<<X[i]);
	}
	if(S%2) return {};
	S/=2;
	if(HB[N][S]==0) return {};
	for(i=N-1;i>=0;i--) {
		if(S>=X[i]&&HB[i][S-X[i]]) {
			R[0].push_back(X[i]);
			S-=X[i];
		}
		else R[1].push_back(X[i]);
	}
	sort(ALL(R[0]));
	sort(ALL(R[1]));
	if(R[0].size()<R[1].size()) swap(R[0],R[1]);
	
	return {R[0],R[1]};
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		auto A=hoge();
		auto B=hoge();
		
		if(A.empty()||B.empty()) {
			cout<<"No"<<endl;
			continue;
		}
		if(A[0].size()+A[1].size()!=B[0].size()+B[1].size()) {
			cout<<"No"<<endl;
			continue;
		}
		
		x=y=0;
		cout<<"Yes"<<endl;
		if(A[0].size()<=B[0].size()) {
			reverse(ALL(A[0]));
			reverse(ALL(B[1]));
			while(A[1].size()) A[0].push_back(-A[1].back()), A[1].pop_back();
			while(B[1].size()) B[0].push_back(-B[1].back()), B[1].pop_back();
			FOR(i,A[0].size()) {
				x+=A[0][i];
				cout<<x<<" "<<y<<endl;
				y+=B[0][i];
				cout<<x<<" "<<y<<endl;
			}
		}
		else {
			reverse(ALL(A[1]));
			reverse(ALL(B[0]));
			while(A[1].size()) A[0].push_back(-A[1].back()), A[1].pop_back();
			while(B[1].size()) B[0].push_back(-B[1].back()), B[1].pop_back();
			FOR(i,A[0].size()) {
				y+=B[0][i];
				cout<<x<<" "<<y<<endl;
				x+=A[0][i];
				cout<<x<<" "<<y<<endl;
			}
		}
		
	}
}

まとめ

言われてみると簡単なんだけども。