TopCoder, Single Round Match 654, Division 2, Level 1 : SquareScoresDiv2

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13700&rd=16318

問題概要

　文字列 について，その文字列の得点を次のように定める

• インデックスの対 であって，部分文字列 がただ一種類の文字から成るようなものの個数

　文字列 が与えられる． の得点を求めよ．
　

解法

　 を と書きます．
　答えの求め方が問題文で与えられているので，これをそのまま実装すれば解くことができます． の部分文字列の列挙は，部分文字列の始点を全探索し，その内側で終点を全探索する二重ループで列挙することができます．C++ の場合，std::string::substr メンバ関数を使うことで，部分文字列を格納した std::string オブジェクトを得ることができます（使わなくても解けますが，分かりやすたのため別のオブジェクトとして取り出す実装を選びました）．std::string::substr の第一引数は部分文字列の始点を表すインデックス (0-indexdd) で，第二引数は切り出す文字数です．
　さて，残る課題は，切り出した部分文字列がただ一種の文字から成るか否かを判定する部分です．これは，部分文字列内の全ての文字が，部分文字列の先頭の文字と等しいか否かを調べることで判定できます．
　部分文字列の総数が であり，一つの部分文字列に対する判定に 時間かかるので，全体では 時間となります．

コード

#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )
#define ALL( c ) ( c ).begin(), ( c ).end()

#define SZ( v ) ( (int)( v ).size() )

class SquareScoresDiv2
{
public:
	int getscore( string s )
	{
		const int L = SZ( s );

		int res = 0;
		REP( i, L )
		{
			for ( int j = 1; i + j <= L; ++j )
			{
				const string t = s.substr( i, j );
				res += all_of( ALL( t ), bind( equal_to< char >(), _1, t[0] ) );
			}
		}
		return res;
	}
};