TopCoder SRM 609, Division 2, Level 1 : MagicalStringDiv2

問題文

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

問題概要

　文字列 X について、正整数 k であって、k 個の連続する '>' と K 個の連続する '<' を連結することで X となる k が存在する場合に限り、X は magical であるとする。
　文字列 S が与えられる。S に関して '>' と '<' を相互に置き換える操作が可能なとき、S を magical にするために必要な操作回数の最小を求めよ。

解法

　まず、同じ文字について 2 回以上操作をするのは無駄になるので、各文字に関して、操作回数は高々 1 回です。従って、異なる文字に変換されなければならない文字の数を数えればよいことになります。
　S の長さを L とします。文字列の長さは不変なので、題意より、区間 [ 0, L / 2 ) の位置にある文字は '>' にならなければならず、それ以外は '<' にならなければなりません。全ての文字に関して目標状態が確定してるので、それに合致しない文字の数を数えれば、それが答えになります。

コード

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

class MagicalStringDiv2
{
public:
	int minimalMoves( string S )
	{
		const int L = S.size();

		int res = 0;
		REP( i, 0, L )
		{
			if ( i < L / 2 )
			{
				res += S[i] == '<';
			}
			else{
				res += S[i] == '>';
			}
		}
		return res;
	}
};