TopCoder SRM 781 : Div1 Easy EpicPartition

Easyが無事通ってよかった。
https://community.topcoder.com/stat?c=problem_statement&pm=15954&rd=17857

問題

整数Nが与えられる。
1～6Nの整数を以下の3つの集合A,B,Cに分けたい。

• A,B,Cの要素数は等しい。
• sum(A)*2=sum(B)*2=sum(C)

答え方としては、6N文字の文字列を作り、i文字目にはiがどこに属するか"a""b""c"で答える。

解法

1～6Nの総和が4の倍数でないといけないのは自明なのでそれだけチェックする。
まずsum(A)=sum(B)を満たす状態を作り、そのあとそれをキープしたままsum(A)*2=sum(C)を作ろう。

"abba"をN回繰り返したものに"c"を2N個つけると、前者を満たせる。
"abc"または"bac"の並びを"cab""cba"にすると、sum(A)・sum(B)を1増やしsum(C)を2減らすことができる。
もともとsum(A)*2とsum(C)の差は4の倍数なので、これで問題なくいずれ条件を満たす文字列が作れる。

class EpicPartition {
	public:
	string createPartition(int N) {
		int sum=0;
		int i;
		if(N%4) return "";
		string S;
		int A=0,C=0;
		int cur=1;
		FOR(i,N) {
			S+="abba";
			A+=cur+cur+3;
			cur+=4;
		}
		FOR(i,N) {
			S+="cc";
			C+=cur+cur+1;
			cur+=2;
		}
		int x,y;
		for(x=0;x<S.size();x++) if(S[x]=='c') {
			y=x;
			while(A*2<C) {
				if(y==0 || S[y-1]=='c') break;
				swap(S[y],S[y-1]);
				swap(S[y-1],S[y-2]);
				A++;
				C-=2;
				y-=2;
			}
			
		}
		
		
		cout<<A<<" "<<C<<" "<<S<<endl;
		return S;
		
	}
}

まとめ

みんな解法がそれぞれでChalできなかった。