TopCoder, Single Round Match 652, Divisino 2, Level 1 : ValueOfString

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13678&rd=16316

問題概要

　英小文字からなる文字列 が与えられる．また， 番目（1-based）のアルファベットに値 を割り当てる．各文字の値を などと表記する．
　更に， の値を次のように定める． の各文字 について， 以下（等しいか，アルファベット順序で より手前にある文字）の数を とする．文字列 の値は， を各 について求めた和であるとする．
　 の値を求めよ．

解法

　 の長さ を と書きます．
　問題文で示された値の求め方をそのまま実装することで解くことができます．詳しく言うと，まず を総当りします．各 に対応する の値は文字列を走査することで計算することができ， は既知です．つまり，各 に対して文字列を一回走査すればその によって加算される値が求まります．
　着目する文字の数は であり，文字列の走査も 1 回あたり 時間でできるので，全体では 時間になります．

コード

#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) ( c ).begin(), ( c ).end()

class ValueOfString
{
public:
	int findValue( string s )
	{
		int res = 0;
		FOR( c, s )
		{
			res += ( c - 'a' + 1 ) * count_if( ALL( s ), bind( less_equal< char >(), _1, c ) );
		}
		return res;
	}
};