Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-10-01Google Code Jam Japan 2011 予選

Google Code Jam Japan 2011 予選 B 最高のコーヒー

| 20:14 | Google Code Jam Japan 2011 予選 B 最高のコーヒー - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 予選 B 最高のコーヒー - SRM diary(Sigmar) Google Code Jam Japan 2011 予選 B 最高のコーヒー - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

Greedy

まだコーヒーの種類が確定していない日の集合をvector <pair <ll, ll> > empで表す

満足度が高いものから順番に、期限ぎりぎりから消費していく

期限ぎりぎりのコーヒーより満足度の低いコーヒーを使っても、満足度の低いほうのコーヒーが余分に減るだけで、何もいいことがない

ということで以上の方針で問題ない

vector <pair <ll, ll> >で表される期間とか、こういうものの管理はとてつもなく面倒くさい。最悪。

案の定バグりまくり。

一通り直してサンプル合った。

Small合わない。

気分転換にCを解くことにする。

・・・

Cを解いて戻ってきた。

とりあえず簡単に全探索のコードが書けるので、それでSmallだけ解いてみる。

解けた。提出。Correct。

先ほどのLarge用の回答と答えが違うところを調べる。

余計なbreak文が一つ入っていたことに気づく。修正。Small合った。

Large提出。

提出時間:Large 1h49m00s


ソースコード

Large用

struct cts {
	ll c;
	ll t;
	int s;
	bool operator<(const cts &o) const {
		if(this->s>o.s) return true;
		if(this->s<o.s) return false;
		if(this->t>o.t) return true;
		if(this->t<o.t) return false;
		if(this->c<o.c) return true;
		return false;
	}
};

ll solve(int N, ll K, vector <ll> &c, vector <ll> &t, vector <int> &s) {
	ll res=0;

	vector <cts> vc(N);
	for(int i=0; i<N; i++) {
		vc[i].c=c[i];
		vc[i].t=t[i];
		vc[i].s=s[i];
	}
	sort(vc.begin(), vc.end());

	vector <pair <ll, ll> > emp;
	emp.push_back(make_pair(0, K));

	for(int i=0; i<N; i++) {
		int last=-1;
		for(int j=0; j<(int)emp.size(); j++) {
			if(emp[j].first<vc[i].t) last=j;
		}
		ll cnt=0;
		vector <pair <ll, ll> > nemp;
		for(int j=last; j>=0; j--) {
			ll rlast=min(emp[j].second, vc[i].t);
			ll ncnt=cnt+(rlast-emp[j].first);
			if(ncnt<vc[i].c) {
				cnt=ncnt;
				if(rlast!=emp[j].second) nemp.push_back(make_pair(rlast, emp[j].second));
			} else {
				for(int k=0; k<j; k++) nemp.push_back(emp[k]);
				if(emp[j].first!=rlast-(vc[i].c-cnt)) nemp.push_back(make_pair(emp[j].first, rlast-(vc[i].c-cnt)));
				if(rlast!=emp[j].second) nemp.push_back(make_pair(rlast, emp[j].second));
				cnt=vc[i].c;
				break;
			}
		}
		res+=vc[i].s*cnt;
		for(int j=last+1; j<(int)emp.size(); j++) nemp.push_back(emp[j]);
		sort(nemp.begin(), nemp.end());
		emp=nemp;
	}
	
	return res;
}

int main() {
	ifstream ifs("input.txt");
	ofstream ofs("output.txt");

	int testcase;
	ifs >> testcase; ifs.ignore();
	for(int testnum=1; testnum<=testcase; testnum++) {
		int N;
		ll K;
		ifs >> N >> K;
		vector <ll> c(N), t(N);
		vector <int> s(N);
		for(int i=0; i<N; i++) {
			ifs >> c[i] >> t[i] >> s[i];
		}
		ll res=solve(N, K, c, t, s);
		ofs << "Case #" << testnum << ": ";
		ofs << res << endl;
	}
}
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111001