問題概要
$M $ 曲の歌があって，歌 $i$ はアイドル $s_i$ にのみ歌うことができる．コンサートで歌 $i$ を歌うと聴衆の幸福度が $h_i$ 上がる．また，各アイドルはコンサート中に高々 1 回しか歌うことができない．
歌う歌を適切に選ぶことで聴衆の幸福度を最大化したときの聴衆の幸福度を求めよ．
$1 \leq M \leq 100$
$1 \leq |s_i| \leq 10$
解法
ある 1 人のアイドル $a$ に着目すると，このアイドルによる幸福度の寄与の最大値は $a$ によって歌われる歌の内の $h$ の最大値 $\max\{ h_i \mid s_i = a \}$ です．これを関係する（$s$ に出現する）全てのアイドルについて求めてから和をとれば，それが答えです．
std::map を使うと std::string をキーとする連想配列を作ることができるので実装が楽です．
この解法の場合，$M $ 個の要素について std::map を操作することになります．std::map へのアクセス時にはキー値の比較が $O( \log M )$ 回発生して，キー値である std::string の比較はその長さの線形時間掛かります．従って，$|s_i|$ の最大値を $L$ とすれば，アクセスには $O( L \log M )$ 時間かかります．$O( M )$ 個の要素について std::map に定数回ずつアクセスするので，前計算部分は $O( LM \log M )$ 時間かかります．和を計算する部分は $O( M )$ 時間なので，全体は $O( LM \log M )$ 時間で完了します．
コード
#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 ) begin( c ), end( c ) #define SZ( v ) ( (int)( v ).size() ) #define snd second class LiveConcert { public: int maxHappiness( vector <int> h, vector <string> s ) { const int M = SZ( h ); map< string, int > m; REP( i, M ) { m[ s[i] ] = max( m[ s[i] ], h[i] ); } return accumulate( ALL( m ), 0, []( const int a, const pair< string, int > &p ){ return a + p.snd; } ); } };
