2015-2016 ACM-ICPC NEERC : F. Gourmet and Banquet

難易度の割に解いた人が少ない？
http://codeforces.com/contest/589/problem/F

問題

N個の料理があり、それぞれ食べられる時間はA[i]～B[i]の間である。

以下のルールで食事を食べたい。

• 各料理、時間１につき１食べることができる。
• 同時に２つ以上の食べることはできない。
• 食べる料理を切り替えるのは整数時刻の時点のみ可能。
• (時間内であれば)同じ料理を複数回食べても良い。

各料理を同量ずつ食べたい場合、最大どれだけの料理を食べることができるか。

解法

各料理を食べる量を1,2,3...と順次多くしていって条件を満たせるか判定すればよい。

時間１毎に食べられる料理の集合を管理し、時間１毎に貪欲にシミュレーションしていく。
料理を食べる順番は単純で、食べられる残り時間が少ない順に食べていけば良い。

int N;
int A[1010],B[1010];
int need[1010];
vector<int> add[100001];
vector<int> del[100001];
set<pair<int,int> > S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i]>>B[i], add[A[i]].push_back(i),del[B[i]].push_back(i);
	
	for(int can=1;can<=10000/N+2;can++) {
		FOR(i,N) need[i]=can;
		
		S.clear();
		for(i=0;i<=10000;i++) {
			FORR(r,del[i]) if(need[r]) {
				cout<<(can-1)*N<<endl;
				return;
			}
			FORR(r,add[i]) S.insert({B[r],r});
			if(S.size()) {
				auto r=S.begin();
				if(--need[r->second]==0) S.erase(S.begin());
			}
		}
	}
}

まとめ

これも難易度の割に正答数少な目。