読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

主に競技プログラミングの問題について書きます

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

問題概要

 英小文字からなる文字列 s が与えられる.また,i 番目(1-based)のアルファベットに値 i を割り当てる.各文字の値を val_a, val_b, \dots などと表記する.
 更に,s の値を次のように定める.s の各文字 s_i について,s_i 以下(等しいか,アルファベット順序で s_i より手前にある文字)の数を k_i とする.文字列 s の値は,k_i \times val_{ s_i } を各 i について求めた和であるとする.
 s の値を求めよ.

解法

 s の長さ |s|L と書きます.
 問題文で示された値の求め方をそのまま実装することで解くことができます.詳しく言うと,まず i を総当りします.各 i に対応する k の値は文字列を走査することで計算することができ,val_{ s_i } は既知です.つまり,各 i に対して文字列を一回走査すればその i によって加算される値が求まります.
 着目する文字の数は \mathrm{ \Theta }( L ) であり,文字列の走査も 1 回あたり \mathrm{ \Theta }( L ) 時間でできるので,全体では \mathrm{ \Theta }( L^2 ) 時間になります.

コード

#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;
	}
};