TopCoder SRM 695 Div1 Easy BearPasswordLexic、Div2 Medium BearPasswordAny

レートが最盛期より600以上低いぞ。
https://community.topcoder.com/stat?c=problem_statement&pm=14366
https://community.topcoder.com/stat?c=problem_statement&pm=14365

問題

a,bのみで構成されたN文字の文字列Sがある。
また数列Xが与えられる。

Sから生成できるi文字の連続部分文字列のうち、１種類の文字だけで構成されるものがX[i-1]個あるとする。
そのような条件を満たすSが存在すれば、そのうち辞書順最小のものを求めよ。
(Div2は辞書順最小縛りがない)

解法

S中でp文字同じ文字が連続していた場合、X[p-1],X[p-2],X[p-3],,,X[0]はそれぞれ1,2,3...,p個ずつ増加する。
そのため、Xが大きい順に見ていくと、X[p-1]が0でないpのうち(存在すれば)最大のものであるとするとき、Sはp個同じ文字が連続しているものをX[p-1]個含む。
また、そのようなp文字をX[p-1]個Sから取り除くと、X[p-2],X[p-3],...はX[p-1]*2,X[p-2]*3,....ずつ減る。

上記処理をXが0になるまで繰り返すことで、そのようなpを列挙することができる。
途中でX[i]が負になったり、pの総和がNにならない場合は条件を満たすSは存在しない。

あとはそのようなp個の同じ文字列が連続するものをうまく並べ、辞書順最小のSを作りたい。
当然、aaaabbbbaaabbbb...とa,bをいくつか交互に並べることになる。
aの個数はpの大きい順、bの個数はpの小さい順で並べる事で辞書順最小のSを作れる。

class BearPasswordLexic {
	public:
	int N;
	
	string findPassword(vector <int> x) {
		N=x.size();
		
		vector<int> V;
		int i,j,sum=0;
		for(i=N;i>=1;i--) while(x[i-1]) {
			sum+=i;
			V.push_back(i);
			for(j=i;j>=1;j--) x[j-1]-=i+1-j;
			for(j=i;j>=1;j--) if(x[j-1]<0) return "";
		}
		
		if(sum!=N) return "";
		string S;
		int turn=0;
		while(V.size()) {
			if(turn==0) {
				FOR(i,V[0]) S+='a';
				V.erase(V.begin());
			}
			else {
				FOR(i,V.back()) S+='b';
				V.pop_back();
			}
			turn ^= 1;
		}
		
		
		return S;
	}
}

まとめ

bも大きい順に並べちゃった…。