TopCoder SRM 783 : Div1 Medium ABBAReplace

すんなり解けたかと思ったけどそうでもなかった。
https://community.topcoder.com/stat?c=problem_statement&pm=15694&rd=17903

問題

A,Bで構成された文字列Sが与えられる。
1ステップで、S内の"AB"の並びをすべて"BA"に置換できるとする。
これ以上置換できなくなるまでのステップ数は何回か。

解法

先頭のBと末尾のAはステップの影響を受けないので外しておく。
左端のAが、すべてのBの右に行くまでのステップ数を考える。

ここで、以下の特性を考えよう。

• B+(A*n)+Bの並びでAがすべてBの右側に行くまでのステップは、(A*(n-1))+B+A+Bのステップと変わらない。

左のBの左にAが並んでいても同じ(たまったAが左のBを超える前に待たされるか、そのあとに待たされるかの違い)。
そこで、一番左を除き、BとBの間は最大1個のAまで残せるようにし、それ以外のAは左側のBの左に移動してしまおう。
そうすると、BとBの間には0個か1個のAが残り、一番左のBの左にAがたまった状態になる。
この時、左端以外ではAはたまらず毎ステップBを越せるので、(たまった左端のAの個数)+(Bの個数)-1が解。

class ABBAReplace {
	public:
	int countSteps(string S, int N, int seed, int threshold) {
		ll state=seed;
		while(S.size()<N) {
			state = (state * 1103515245 + 12345) % (1LL<<31);
			if(state<threshold) S+='A';
			else S+='B';
		}
		vector<int> num;
		num.push_back(0);
		FORR(c,S) {
			if(c=='A') num.back()++;
			else num.push_back(0);
		}
		num.pop_back();
		int i;
		for(i=num.size()-1;i>=1;i--) {
			if(num[i]>1) {
				num[i-1]+=num[i]-1;
				num[i]=1;
			}
		}
		reverse(ALL(num));
		while(num.size()&&num.back()==0) num.pop_back();
		if(num.empty()) return 0;
		return num.size()+num.back()-1;
		
		
	}
}

まとめ

本番は結構いい解法と思ったけどそんなにSubmit早くなかったね。