Codeforces #205 Div2. D. Queue

今回Eは自力で解けたけどDはEditorial見て解いた…
http://codeforces.com/contest/353/problem/D

問題

少年少女が１列に並んでおり、文字列で列の状況が与えられる。
１秒ごとに、少女が右、少年が左に隣接している場合、両者の位置を入れ替えることができる。
列がこれ以上入れ替え不可能になるまでの時間を答えよ。

解法

初期状態で右側にいる少女ほど、入れ替え不可になる時間は長い。
というのも、左側にまだ少年がいる場合、左側の少女と少年の入れ替え処理が終わらないと少年が少女の右に来ないためである。

まず各少女について、入れ替え不可になるときに到達する位置、すなわち左端から何人目に並ぶかを求める。ここから、少女が入れ替え不可になる最短時間を求めることができる。

次に、自分の左側の少女が入れ替え不可になる時間と、自分が入れ替え不可になる時間を比較し、等しいか前者が大きいなら、自分が入れ替え不可となる場所に落ち着く前に、左側の少女に追いついてしまう。
その場合、左側の少女が入れ替え不可になって次の１秒が自分が入れ替え不可になる。

string S;
int A[1000001];

void solve() {
	int f,i,j,k,l, x,y,r,t;
	
	cin>>S;
	r=x=0;
	while(x<S.size() && S[x]=='F') x++;
	S=S.substr(x);
	y=0;
	FOR(i,S.size()) {
		if(S[i]=='F') {
			if(i-y > r) r=i-y;
			else r++;
			y++;
		}
	}
	cout << r << endl;
}

まとめ

つっかえた場合の処理がうまく自力で書けなかった…。