Codeforces #1018 : E. Wonderful Teddy Bears

なんでTeddy Bearなんだろ。
https://codeforces.com/contest/2096/problem/E

問題

P,Bで構成される文字列Sが与えられる。
S中の3文字の連続部分列をソートする、ということを繰り返し、Sをソートしたい。
最小何回でソートできるか。

解法

S中で、"BB"が見つかれば、それをPの手前先頭に持ってくるのには手前の"P"の数だけソートが必要。
同様に、"PP""が見つかれば、それをBの後に持ってくるのにはあとの"B"の数だけソートが必要。

そこで、まずS中の"BB","PP"を取り除こう。
残った文字列はPBPBPBP...PBPBのような形になる。
先頭"PBP"をソートすると専用4文字が"BPPB"になるので、"PP"の塊ができるので後ろの"B"の数だけソートすると、先頭が"BB",末尾が"PP"となって4文字ソートが完了する。

int T,N;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>S;
		
		int LB=0,RB=0,LP=0,RP=0;
		FORR(c,S) {
			if(c=='P') RP++;
			else RB++;
		}
		
		ll ret=0;
		string V;
		FORR(c,S) {
			if(c=='P') {
				if(V.size()&&V.back()=='P') {
					V.pop_back();
					ret+=RB;
					LP--;
					RP--;
				}
				else {
					V.push_back('P');
					LP++;
					RP--;
				}
			}
			else {
				if(V.size()&&V.back()=='B') {
					V.pop_back();
					ret+=LP;
					LB--;
					RB--;
				}
				else {
					V.push_back('B');
					LB++;
					RB--;
				}
			}
		}
		S=V;
		if(S.size()&&S[0]=='B') S=S.substr(1);
		if(S.size()&&S.back()=='P') S=S.substr(0,S.size()-1);
		x=S.size()/2;
		while(x>1) {
			ret+=x;
			x-=2;
		}
		ret+=x;
		cout<<ret<<endl;
		
	}
}

まとめ

テディベアに色が色々あるの知らなかった。