Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-03-09SRM499 Div1

SRM499 Div1 250 ColorfulRabbits

| 20:59 | SRM499 Div1 250 ColorfulRabbits - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM499 Div1 250 ColorfulRabbits - SRM diary(Sigmar) SRM499 Div1 250 ColorfulRabbits - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

サンプル読む限り、同じ数のウサギをカウントして適当に足し合わせるだけにしか見えないけど・・・

書いた→サンプル通った

提出

うーん・・・合ってるよな・・・


ソースコード

class ColorfulRabbits {
public:
	int getMinimum(vector <int> rep) {
		int res=0;
		int n=rep.size();

		map <int, int> cnt;
		for(int i=0; i<n; i++) {
			cnt[rep[i]]++;
		}

		for(map <int, int>::iterator mpi=cnt.begin(); mpi!=cnt.end(); mpi++) {
			int v=mpi->first+1;
			res+=mpi->second/v*v;
			if(mpi->second%v>0) res+=v;
		}
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110309