TopCoder Open, Algorithm, Round 1A, Level 1 : EllysSortingTrimmer

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12971&rd=15942

問題概要

　文字列 S と整数 L ( <= |S| ) が与えられる。S の L 文字からなる連続する部分列を選んで昇順に並び替え、選んだ部分列より後ろの文字を全て削除する操作を任意回できる。作ることができる文字列のうちで辞書順最小ののものを求めよ。

解法

　後ろの方に辞書式順序で小さい文字が存在するならば、操作によって手前にもってきた方が小さな文字列を構成できます。従って、選択可能な最も後ろの位置から前方向に向かって操作を繰り返して、最後に残った文字列が最適です。

コード

class EllysSortingTrimmer
{
public:
	string getMin( string S, int L )
	{
		const int N = S.size();

		for ( int i = N - L; 0 <= i; i-- )
		{
			sort( S.begin() + i, S.begin() + i + L );
		}
		return string( S.begin(), S.begin() + L );
	}
};