Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-12-31SRM528 Div1(Practice)

SRM528 Div1 250 Cut

| 21:33 | SRM528 Div1 250 Cut - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM528 Div1 250 Cut - SRM diary(Sigmar) SRM528 Div1 250 Cut - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

eelって何だと思ったらウナギらしい。最初文意からしてソバかと思った。

しかしウナギってanguilla(アンギラ)じゃなかったっけ、、と思ったらアンギラは学名だそうだ。ふーん・・


解法は単に10で割れるものから優先的に切るだけ。

10で割れるものの中でも短いものを優先的に切る。

なぜならピッタリ切れると得するのが10で割れるものだけで、なるべくピッタリを増やすほうが得だから。


あんまり難しくはないと思ったけど随分pass率が低かったみたい。なぜだろう。


class Cut {
public:
	int getMaximum(vector <int> eellen, int maxc) {
		int res=0;
		int n=eellen.size();

		vector <int> e10, eelse;
		for(int i=0; i<n; i++) {
			if(eellen[i]%10==0) e10.push_back(eellen[i]);
			else eelse.push_back(eellen[i]);
		}
		sort(e10.begin(), e10.end());
		sort(eelse.begin(), eelse.end());//10で割れないものはたぶんソートしなくていい

		for(int i=0; i<(int)e10.size(); i++) {
			if(e10[i]==10) res++;//たぶん長さ10を特別扱いしなくていい
			else {
				if(e10[i]/10-1<=maxc) {
					res+=e10[i]/10;
					maxc-=e10[i]/10-1;
				} else {
					res+=maxc;
					maxc=0;
				}
			}
		}

		for(int i=0; i<(int)eelse.size(); i++) {
			if(eelse[i]/10<=maxc) {
				res+=eelse[i]/10;
				maxc-=eelse[i]/10;
			} else {
				res+=maxc;
				maxc=0;
			}
		}
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111231