TopCoder SRM 609, Division 1, Level 1 : MagicalStringDiv1

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13003&rd=15842

問題概要

　文字列 X について、非負整数 k であって、k 個の連続する '>' と k 個の連続する '<' を連結することで X となる k が存在するときに限り、X は magical であるとする。k = 0 の場合、空文字列も magical となる。
　文字列 S が与えられる。S に関して、任意の文字を削除する操作が可能である。S を magical な文字列に変換するために必要な操作回数の最小を求めよ。

解法

　変換し終わったとき、ある位置より手前は全て '>' となり、それ以外は全て '<' となります。文字列の長さが高々 50 なので、この「ある位置」を全て試すことができます。分割点が決まったとき、それより手前の '<' は全て削除される必要があり、それ以降の '>' もまた全て削除される必要があると分かります。このようにして、それぞれの仮定された分割点に関して必要な手数を計算し、最小のものを return すればよいです。

コード

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

class MagicalStringDiv1
{
public:
	int getLongest( string S )
	{
		const int L = S.size();

		int res = 0;
		REP( i, 0, L + 1 )
		{
			int cnt1 = 0, cnt2 = 0;
			REP( j, 0, L )
			{
				if ( j < i )
				{
					cnt1 += S[j] == '>';
				}
				else
				{
					cnt2 += S[j] == '<';
				}
			}
			res = max( res, min( cnt1, cnt2 ) * 2 );
		}

		return res;
	}
};