まぁまぁの出来だった回。
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; } }
まとめ
今思えばもっと短く書けそう。