kmjp's blog

競技プログラミング参加記です

Pinely Round 2 : E. Speedrun

まぁまぁの出来だった回。
https://codeforces.com/contest/1863/problem/E

問題

N個のタスクがある。
1日はK時間あり、各タスクiは、毎日H[i]時にしか行えない。
また、一部のタスクの対には依存関係があり、先に行わなければならないタスクが指定される。
なお、同じ時間に複数タスクを行ってもよい。

最適なタイミングで最初のタスクを開始した場合、全タスクを終える最短時間はいずれか。

解法

0~(K-1)時のどこかで最初のタスクを行うとする。
その場合、各タスクの実行時間は最悪ケースと最良ケースで高々1日、K時間までしか変わらない。
この様子をシミュレートしよう。

最初のタスクの開始時刻を遅らせるたび、その影響を受けて開始が1日遅れるタスクをシミュレートする。
このシミュレートの過程で、高々N回しかタスクを遅らせる処理は起きない。
それぞれのケースで最初のタスクと最後のタスクの時間の差を取ればよい。

int T;
int N,M,K;
ll H[202020];
ll C[202020];
int in[202020],in2[202020];
vector<int> E[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M>>K;
		FOR(i,N) {
			E[i].clear();
			in[i]=in2[i]=0;
		}
		
		FOR(i,N) {
			cin>>C[i];
			H[i]=C[i];
		}
		FOR(i,M) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			in[y-1]++;
			in2[y-1]++;
		}
		priority_queue<pair<ll,int>> Q;
		FOR(i,N) if(in[i]==0) {
			Q.push({-H[i],i});
		}
		while(Q.size()) {
			ll co=-Q.top().first;
			int x=Q.top().second;
			Q.pop();
			FORR(e,E[x]) {
				if(C[e]>=C[x]) {
					H[e]=max(H[e],H[x]+(C[e]-C[x]));
				}
				else {
					H[e]=max(H[e],H[x]+(C[e]+K-C[x]));
				}
				in[e]--;
				if(in[e]==0) Q.push({-H[e],e});
			}
		}
		multiset<ll> Ts;
		vector<pair<ll,int>> cand;
		FOR(i,N) {
			Ts.insert(H[i]);
			if(in2[i]==0) cand.push_back({H[i],i});
		}
		ll ma=*Ts.rbegin()-*Ts.begin();
		sort(ALL(cand));
		FORR2(h,i,cand) {
			Ts.erase(Ts.find(H[i]));
			H[i]+=K;
			Ts.insert(H[i]);
			Q.push({-H[i],i});
			while(Q.size()) {
				ll co=-Q.top().first;
				int x=Q.top().second;
				Q.pop();
				if(H[x]!=co) continue;
				FORR(e,E[x]) {
					ll ne;
					if(C[e]>=C[x]) {
						ne=H[x]+(C[e]-C[x]);
					}
					else {
						ne=H[x]+(C[e]+K-C[x]);
					}
					if(ne>H[e]) {
						Ts.erase(Ts.find(H[e]));
						H[e]=ne;
						Ts.insert(H[e]);
						Q.push({-H[e],e});
					}
				}
			}
			ma=min(ma,*Ts.rbegin()-*Ts.begin());
			
		}
		cout<<ma<<endl;
	}
}

まとめ

今思えばもっと短く書けそう。