TopCoder SRM 769 : Div1 Medium SchedulingWoes

ちょっと手間取ったけど解ききれてよかった。
https://community.topcoder.com/stat?c=problem_statement&pm=15756

問題

これからN科目のテストが行われる。
各テストiは、今からD[i]日後の午後に行われ、それに受かるには午前中をT[i]回その科目に専念して勉強しないといけない。

毎日午前中は1科目だけ専念できる。一方テストは同日実施の物は複数受けることができる。
最適な順で勉強した場合、最大何科目のテストに合格できるか。

解法

D[i]昇順にソートし、multisetやpriority_queueで受かる試験の必要勉強日数の集合とその和を管理して以下判定していこう。

次に受けるテストを考えたとき、

• 今行うことが確定しているここまでの勉強日数に対し、次受けるテストの勉強時間を入れる余裕があるなら入れる。
• 上記余裕はないが、multisetやpriority_queueに次受けるテストより勉強時間が長いものがあれば、それと差し替える。これは受かる科目数は変わらず、必要勉強時間は減るので常に得である。

class SchedulingWoes {
	public:
	
	int study(int N, int seed, vector <int> Dprefix, int maxD, vector <int> Tprefix, int factor) {
		vector<ll> ran;
		ran.push_back(seed);
		int i;
		for(i=1;i<2*N;i++) {
			ran.push_back((ran.back()*1103515245+12345)%(1LL<<31));
			//cout<<ran[i]<<endl;
		}
		
		vector<pair<ll,ll>> P;
		FOR(i,Dprefix.size()) {
			P.push_back({Dprefix[i],Tprefix[i]});
		}
		for(i=Dprefix.size();i<N;i++) {
			ll D=1+ran[2*i]%maxD;
			ll maxT=max(1LL,D/factor);
			ll T=1+ran[2*i+1]%maxT;
			P.push_back({D,T});
		}
		sort(ALL(P));
		multiset<ll> S;
		ll tot=0;
		FORR(p,P) {
			
			if(p.first-tot>=p.second) {
				S.insert(p.second);
				tot+=p.second;
			}
			else if(S.size() && p.second<*S.rbegin()) {
				tot-=*S.rbegin();
				S.erase(S.find(*S.rbegin()));
				S.insert(p.second);
				tot+=p.second;
			}
		}
		return S.size();
	}
}

まとめ

乱数使ったデータ生成の部分でバグを仕込んで回答が遅れてしまった。
この入力形式面白くないしやめてほしいなぁ。