Codeforces #604 Div1 B. Beautiful Sequence

本番残念ながら落とした。
http://codeforces.com/contest/1264/problem/B

問題

0,1,2,3がa,b,c,d回ずつ現れるような整数列のうち、隣接要素の差が1となるものを構築可能か。
可能なら構築せよ。

解法

数列中に0を出したい場合、1→0→1の順に登場するの一択。
同様に3を出す場合2→3→2の一択。
なので、基本的に1と2を往復しつつ、0,3が余ってるならそのつど0,1を通ろう。

最初だけ0-3のどれで始めるか総当たりするとよい。

int X[4];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X[0]>>X[1]>>X[2]>>X[3];
	FOR(x,4) {
		int Y[4];
		FOR(i,4) Y[i]=X[i];
		vector<int> C;
		int cur=x;
		while(1) {
			if(Y[cur]==0) break;
			Y[cur]--;
			C.push_back(cur);
			if(cur==0) {
				cur=1;
			}
			else if(cur==3) {
				cur=2;
			}
			else if(cur==1) {
				if(Y[0]) cur=0;
				else cur=2;
			}
			else {
				if(Y[3]) cur=3;
				else cur=1;
			}
		}
		
		if(C.size()==X[0]+X[1]+X[2]+X[3]) {
			cout<<"YES"<<endl;
			FORR(v,C) cout<<v<<" ";
			cout<<endl;
			return;
		}
	}
	cout<<"NO"<<endl;
	
}

まとめ

本番オイラーパスとか頑張ったんだけどな。