Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-10-05SRM520 Div1

SRM520 Div1 250 SRMCodingPhase

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

Problem Statement

コーディングフェーズ

どう見てもイテレーションするだけ。

随分計算量が余裕すぎる。まあいいか・・・

書いた

ストレートフォワードに書いたらえらくもっさりしたコードになった


ソースコード

割り振るluckを全探索して、解く順番を全探索する

しかし、解く問題を2^3のビットマスクで決めて、得点の高い問題からGreedyにluckを割り振ったほうが書くのは楽そうだと思った

class SRMCodingPhase {
public:
	int countScore(vector <int> points, vector <int> skills, int luck) {
		int res=0;

		int mul[3]={2,4,8};
		int l[3];
		for(l[0]=0; l[0]<=luck; l[0]++) {
			for(l[1]=0; l[1]<=luck-l[0]; l[1]++) {
				l[2]=luck-l[0]-l[1];
				vector <int> sk(3);
				for(int i=0; i<3; i++) sk[i]=max(1, skills[i]-l[i]);
				vector <int> perm(3);
				for(int i=0; i<3; i++) perm[i]=i;
				do {
					int pass=0;
					int sum=0;
					for(int i=0; i<3; i++) {
						if(75-pass>=sk[perm[i]]) {
							pass+=sk[perm[i]];
							sum+=points[perm[i]]-sk[perm[i]]*mul[perm[i]];
						}
					}
					res=max(res, sum);
				} while(next_permutation(perm.begin(), perm.end()));
			}
		}

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111005