SRM 669 div2

Easy

問題文

M曲の歌がある. 歌は0~M-1でナンバリングされ、i番目の歌は、idol s[i]のみ歌うことができる.
i番目の歌が歌われると観客の幸福度がh[i]増える.

各idolは、多くて1曲しか歌うことができない.
この条件の下、観客の幸福度を最大化せよ.

入力は、s[i]とh[i]が与えられる.

制約

• 1 ≤ M ≤ 100

解法

各idolについて、歌える歌の中で、幸福度が最大になるものを選ぶ.
この最大値の和が答え.

文字列に対する最大値を得るためにはmapなどのSTLを使うと楽.

コメント

誤読して落ちてしまった…

コード

class LiveConcert {
public:
    int maxHappiness(vector <int> h, vector <string> s) {
	map<string,int> mp;
	for(int i = 0 ; i < (int)s.size() ; i++){
	    if(mp.count(s[i])) mp[s[i]] = max(mp[s[i]],h[i]);
	    else mp[s[i]] = h[i];
	}
	int res = 0;
	for(auto x : mp){
	    res += x.second;
	}
	return res;		   
    }
}

Med

問題文

スライムがN体いる. スライムはそれぞれ、初期のサイズa[i]である.
任意の2体のスライムを選ぶ. それらのスライムを合体する.
合体すると、スライムは1体になり、サイズはその2体のスライムのサイズの和となる.
そして、2体のスライムのサイズの積のmascotsを得ることができる.

最適の順で合体させたときの得られるmascotsの最大値を求めよ.

解法

priority_queueを使うよくある問題かと思いきやそうではない. (それでも通る)

実は、どの順で合体しても最適になる.（おそらく）

コメント

なんでこれがMedなのかよくわからない.

コード

class CombiningSlimes {
public:
    int maxMascots(vector <int> a) {
	priority_queue<int,vector<int>,greater<int>> Q;
	for(auto x : a) Q.push(x);
	int res = 0;
	while(Q.size() != 1){
	    int l1 = Q.top(); Q.pop();
	    int l2 = Q.top(); Q.pop();
	    res += l1*l2;
	    Q.push(l1+l2);
	}
	return res;	   
    }
}