読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder SRM 606, Division 2, Level 1 : EllysSubstringSorter

問題概要

 英大文字からなる文字列が与えられる。この文字列のうち、連続する L 文字をアルファベット順にソートする操作が一回だけできる。この操作により作ることができる文字列の内、辞書順最小のものを求めよ。

解法

 ソートする位置を全部試して、できた文字列の内最小のものを返すことで解くことができます。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class EllysSubstringSorter
{
public:
	string getMin( string S, int L )
	{
		set<string> res;

		REP( i, 0, S.size() - L + 1 )
		{
			string s = S;
			sort( s.begin() + i, s.begin() + i + L );
			res.insert( s );
		}

		return *res.begin();
	}
};