AtCoder ABC #304 (東京海上日動プログラミングコンテスト2023) : Ex - Constrained Topological Sort

EXの方が簡単だった。
https://atcoder.jp/contests/abc304/tasks/abc304_h

問題

1～Nの順列Pを作りたい。
以下の条件を満たすものは構築可能か、可能なら一例を示せ。

• i番目の要素はL[i]以上R[i]以下でなければならない。
• P[i]＜P[j]でなければならない、という(i,j)の対が多数与えられる。

解法

後者の条件が循環している場合、解なし。
そうでない場合、要素間の大小関係はDAGを成す。

vに対し、P[v]＜P[w]という条件が与えられたｗからなる数列をWとする。
もしP[v]を定めた場合、P[w[0]],P[w[1]],...P[w[i]]は最低でもP[v]+1,P[v]+2,...P[v]+i+1以上でなければならない。

そこで、wをR[w]の小さい順に置き換える。
するとR[v]＜min(R[w[i]]-i)でなければならない。

よって、P[v]＜P[w]の条件をもとに各要素をトポロジカルソートし、Rの上限を定めていこう。
あとは、Rの上限の小さい要素P[i]に、貪欲に1,2,3....を当てはめて行けばよい。

int N,M;
vector<int> E[202020],RE[202020];
int in[202020],in2[202020];
int L[202020],R[202020];
int P[202020];
vector<int> ev[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		RE[y-1].push_back(x-1);
		in[x-1]++;
		in2[y-1]++;
	}
	FOR(i,N) {
		cin>>L[i]>>R[i];
	}
	queue<int> Q;
	FOR(i,N) if(in[i]==0) Q.push(i);
	while(Q.size()) {
		int cur=Q.front();
		Q.pop();
		vector<int> C;
		FORR(e,E[cur]) {
			C.push_back(R[e]);
		}
		sort(ALL(C));
		FOR(i,C.size()) R[cur]=min(R[cur],C[i]-(i+1));
		FORR(e,RE[cur]) if(--in[e]==0) Q.push(e);
		in[cur]=-1;
	}
	
	FOR(i,N) {
		if(in[i]>=0) {
			cout<<"No"<<endl;
			return;
		}
		if(L[i]>R[i]) {
			cout<<"No"<<endl;
			return;
		}
		if(in2[i]==0) ev[L[i]].push_back(i);
	}
	set<pair<int,int>> cand;
	for(i=1;i<=N;i++) {
		FORR(e,ev[i]) {
			cand.insert({R[e],e});
		}
		if(cand.empty()) {
			cout<<"No"<<endl;
			return;
		}
		x=cand.begin()->second;
		cand.erase(cand.begin());
		if(R[x]<i) {
			cout<<"No"<<endl;
			return;
		}
		P[x]=i;
		FORR(e,E[x]) {
			--in2[e];
			if(in2[e]==0) {
				if(L[e]<=i) {
					cand.insert({R[e],e});
				}
				else {
					ev[L[e]].push_back(e);
				}
			}
		}
	}
	cout<<"Yes"<<endl;
	FOR(i,N) cout<<P[i]<<" ";
	cout<<endl;
	
}

まとめ

これ一発で通せたのは良かったね。