Codeforces 353D - Queue

問題文 : Queue

概要 :
長さ$n$ の文字列があり, 'M' と'F' から構成されている. 1 ターンの間に次の動作を行う :
"MF" という部分文字列を"FM" に置き換える.

文字列が"FF.....MM" という形になるのは何ターン後か？

$n \leqq 10^6$

解法 :

まず, 先頭にあるF は無視する. 最後のF 所定の位置に移動するまでの時間がわかれば良い.
とりあえず自分より前にあるM 以上のターンがかかるのは分かる. 問題は, 部分列を交換している間にどれくらい"待つ" 必要があるかということになる.
これは, max(前の人との距離 - 今までの待ち時間 + 1, 0) で求まる. これを$w$ とすると, 答えは$w$ + 自分の前にいる'M' の数になる.

先頭から確かめられるため$O(n)$ 時間でこの問題を解ける.

コード :

#include <cstdio>

using namespace std;

int main()
{
	static char s[1000001];
	
	scanf("%s", s);
	
	int ret = 0, w = 0, tmp = 0, tot = 0;
	for (int i = 0; s[i]; i++){
		if (s[i] == 'M'){
			tmp++; tot++;
		}
		else {
			w = max(w - tmp + 1, 0);
			if (tot) ret = tot + w;
			else w = 0;
			tmp = 0;
		}
	}
	printf("%d\n", ret);
	
	return (0);
}