Google Code Jam 2016 Round1A : A. The Last Word

R2進出できたので、これで安らかにGWに突入できる。
https://code.google.com/codejam/contest/4304486/dashboard#s=p0

問題

文字列Sが与えられる。
ここから以下の手順で新たな文字列Tを作る。

• 初期状態でTは空文字列。
• Sの先頭から1文字ずつ、Tの先頭か末尾に加えていく。

Tとして考えられる文字列のうち、辞書順最後尾のものを求めよ。

解法

今処理中の文字が、Tの先頭より辞書順で小さいなら末尾に、そうでなければ先頭に追加していけば良い。

void solve(int _loop) {
	int f,i,j,k,l,x,y;

	string S,T;
	cin>>S;
	FORR(r,S) {
		if(T.empty() || r<T[0]) T+=r;
		else T=r+T;
	}
	
	_P("Case #%d: %s\n",_loop,T.c_str());
}

まとめ

蟻本の問題と近いと思ったけど微妙に違うのかな。