Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-10-03Google Code Jam Japan 2011 予選(復習)

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

| 00:43 | 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

K日目から1日目に向かって遡っていく

その時点で最も満足度の高いコーヒーを飲むようにする

これで前のやり方(満足度の高いものから消費する日を決める)より全然楽にコードが書ける


ソースコード

main関数は省略

//コーヒーの各パラメータを構造体にする
//比較関数は期限にしている
struct cts {
	ll c, t, s;
	bool operator<(const cts &o) const {
		if(this->t>o.t) return true;
		return false;
	}
};

//priority_queue用に満足度をキーにする比較関数を作成
struct less2 {
	bool operator()(const cts &a, const cts &b) {
		if(a.s<b.s) return true;
		return false;
	}
};

ll solve(int N, ll K, vector <ll> &c, vector <ll> &t, vector <ll> &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 <ll> tlist;
	tlist.push_back(0);
	for(int i=0; i<N; i++) tlist.push_back(t[i]);
	sort(tlist.begin(), tlist.end(), greater <ll>());

	//期限の来たものから、priority_queueに突っ込んでいる
	//今使えるコーヒーのうち、満足度の最高のものを使うようにしている
	priority_queue <cts, vector <cts>, less2> pq;
	for(int i=0; i<N; i++) {
		pq.push(vc[i]);
		ll interval=tlist[i]-tlist[i+1];
		while(!pq.empty()) {
			cts qt=pq.top(); pq.pop();
			if(qt.c>interval) {
				res+=qt.s*interval;
				qt.c-=interval;
				pq.push(qt);
				break;
			} else {
				res+=qt.s*qt.c;
				interval-=qt.c;
			}
		}
	}
	
	return res;
}

(10/5追記)

満足度順で取っていく手法でも効率的な方法があるとのことでコメントいただきました。こんなに多くの解き方があるとは、とても実装の練習に良い題材ですね。

tozangezanさんのブログ

tozangezantozangezan2011/10/04 16:12満足度順にとっていくのでも区間を持たないとこれより楽に実装できると思うのですが

SigmarSigmar2011/10/05 20:42コメントありがとうございます。
勝手ながら検索してtozangezanさんのコードを読ませていただきました。
区間を持たないというのは、飲んだ日の分、日数を圧縮するようなイメージで、その区間より後ろにある期限を単純に日数分前に持ってくるという手法ですね。これは思いつきませんでした。紹介の意味でリンクさせていただきます。

odoroimodoroim2019/10/22 12:47http://mewkid.net/buy-xalanta/ - Amoxil <a href="http://mewkid.net/buy-xalanta/">Amoxicillin No Prescription</a> iut.crgg.topcoder.g.hatena.ne.jp.ghm.rj http://mewkid.net/buy-xalanta/

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111003