TopCoder SRM 647 Div2 Medium TravellingSalesmanEasy

SRM647に参加。
EasyもMediumもあまり回答速くなかったけど、1Challengeも合わせ2完。
ようやくCFに続きTopCoderでもRedCoderになりました。
http://community.topcoder.com/stat?c=problem_statement&pm=13631

問題

1～M番のM個の町がある。
商人はこれらの町を配列visit[i]に格納された順に回っていく。
city[i]・profit[i]には、商品を買いたい人のいる町と、商品を売ったときの利益が格納されている。

商人が町を１回訪問するごとに１個ものを売ることができるとき、最大の利益を答えよ。

解法

まず各町について、商品を買いたい人をprofitの高い順に並べる。
後はvisit順に町を訪問し、その町で(まだ商品を買っていない)最大のprofitの人に商品を売ればよい。

class TravellingSalesmanEasy {
	public:
	int getMaxProfit(int M, vector <int> profit, vector <int> city, vector <int> visit) {
		int i,x,y;
		vector<int> P[101];
		vector<int> PP;
		FOR(i,profit.size()) P[city[i]-1].push_back(profit[i]);
		FOR(i,100) sort(P[i].begin(),P[i].end());
		int mp=0;
		FOR(i,visit.size()) {
			if(P[visit[i]-1].size()) {
				mp+=P[visit[i]-1].back();
				P[visit[i]-1].pop_back();
			}
		}
		return mp;
	}
}

まとめ

Div2 Mediumにしては簡単過ぎない？と思ったら、案の定回答率や平均得点がかなり高い。