TopCoder SRM 593, Division 2, Level 1 : RaiseThisBarn

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12780&rd=15705

概要

'.', 'c' からなる文字列が与えられる。
この文字列を空でない二つの文字列であって 'c' の数が等しい文字列に分割する方法はいくつあるか求めよ。

解法

分割する点を全て試し、それぞれについて 'c' の数を数えることで解くことができます。

コード

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

class RaiseThisBarn
{
public:
	int calc( string str )
	{
		const int N = str.size();
		
		int res = 0;
		REP( k, 1, N )
		{
			int a = 0, b = 0;
			REP( i, 0, N )
			{
				( i < k ? a : b ) += str[i] == 'c';
			}
			res += a == b;
		}

		return res;
	}
};