Codeforces #411 Div1 B. Minimum number of steps

一瞬難しそうでびっくりした。
http://codeforces.com/contest/804/problem/B

問題

'a''b'で構成される文字列Sがある。
S中部分文字列で'ab'が登場する場合、'bba'で置き換える、という作業を繰り返す。
これ以上置き換えができなくなるまでの最小回数を求めよ。

解法

Sの末尾から考えていこう。
S[i+1]...S[|S|-1]について作業が完了しているとする。
するとS[i+1]...S[|S|-1]の処理完了後は、bがいくつか続いた後aが続く形となる(そうでなければaのあとbが来る箇所があるので、まだ作業が可能である)
S[i]が'a'だった場合、直後の'b'とswapし、その際'b'の数を倍にする、という作業を'b'の数だけ繰り返すことになる。

よって、Sの末尾から順に、処理回数と残っている'b'の数を更新していけばよい。

string S;
int N;
ll mo=1000000007;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	
	ll ret=0;
	ll nb=0;
	for(i=N-1;i>=0;i--) {
		if(S[i]=='b') nb++;
		else {
			(ret += nb)%=mo;
			nb=nb*2%mo;
		}
	}
	
	cout<<ret<<endl;
	
}

まとめ

結構あっさり。