Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-07-18SRM476 Div1

SRM476 Div1 250 Badgers

| 13:49 | SRM476 Div1 250 Badgers - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM476 Div1 250 Badgers - SRM diary(Sigmar) SRM476 Div1 250 Badgers - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→読みにくい・・

→つまり、、2匹以上の場合のみgreed[i]だけ追加の餌が必要ということなのかな?

→あ、違う、よく読んだら他のbadger1匹につきgreed[i]の餌が追加で必要ということか

→えーと・・たかだか50匹しかいないので、x匹飼えるかどうか全部試せばOKかな

→書く→サンプル合わない

→何やら色々書き間違っている→直す→サンプル合う

→コーナーケースは・・0匹と最大匹数を確認、問題なし

→提出

→500へ


チャレンジフェーズ

→狙いどころは0と最大値のコーナーケースくらいか・・

→全員0から最大値までちゃんと見てますね

→特になにもせず


システムテスト

→Passed


以下、ソースです。

ちょっと問題読解とミス修正で時間を取りすぎた・・


class Badgers {
public:
	int feedMost(vector <int> hunger, vector <int> greed, int totalFood) {
		int res;
		int bsz=hunger.size();

		for(res=bsz; res>0; res--) {
			vector <int> f(bsz);
			for(int i=0; i<bsz; i++) {
				f[i]=hunger[i]+greed[i]*(res-1);
			}
			sort(f.begin(), f.end());
			if(accumulate(f.begin(), f.begin()+res, 0)<=totalFood) return res;
		}
		return 0;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100718