AtCoder ARC #165 : D - Substring Comparison

うーん、方針が合わなかった。
https://atcoder.jp/contests/arc165/tasks/arc165_d

問題

N要素の整数列Xがあるとする。
部分列X[A,B]がX[C,D]より辞書順で小さい、という条件が多数与えられる。
条件を満たすXが存在するか判定せよ。

解法

X[A]＜X[C]にして問題ないなら、さっさとそうしてしまった方がよい。
またX[A]==X[C]なら、X[A+1,B]がX[C+1,D]より小さいという問題に置き換えられる。

各条件に対し、X[A]≦X[C]を仮定し、N頂点の無向グラフを考えてA→Cに辺を張ろう。
もしこのグラフに閉路が無いなら、トポロジカルソート順にX[A]やX[C]を設定することで条件を満たせる。
閉路がある場合、union-findを用いて、閉路に相当するindex IについてA[I]がすべて同じという条件を設けよう。
この時、X[A]==X[C]なら、X[A+1,B]がX[C+1,D]より小さいという問題に置き換え続ければよい。

int N,M;
int A[2020],B[2020],C[2020],D[2020];

vector<int> X[2020];
vector<int> Y[2020];

class SCC {
public:
	static const int MV = 2020;
	vector<vector<int> > SC; int NV,GR[MV];
private:
	vector<int> E[MV], RE[MV], NUM; int vis[MV];
public:
	void init(int NV) { this->NV=NV; for(int i=0;i<NV;i++) { E[i].clear(); RE[i].clear();}}
	void add_edge(int x,int y) { E[x].push_back(y); RE[y].push_back(x); }
	void dfs(int cu) { vis[cu]=1; for(int i=0;i<E[cu].size();i++) if(!vis[E[cu][i]]) dfs(E[cu][i]); NUM.push_back(cu); }
	void revdfs(int cu, int ind) { int i; vis[cu]=1; GR[cu]=ind; SC[ind].push_back(cu);
		FOR(i,RE[cu].size()) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);}
	void scc() {
		int c=0,i; SC.clear(); SC.resize(NV); NUM.clear();
		assert(NV);
		FOR(i,NV) vis[i]=0; FOR(i,NV) if(!vis[i]) dfs(i); FOR(i,NV) vis[i]=0;
		for(int i=NUM.size()-1;i>=0;i--) if(!vis[NUM[i]]){
			SC[c].clear(); revdfs(NUM[i],c); sort(SC[c].begin(),SC[c].end()); c++;
		}
		SC.resize(c);
	}
};
SCC scc;

template<int um> class UF {
	public:
	vector<int> par,rank,cnt,G[um];
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
	void dump(int num=um) { //グループ分けした配列を作る
		int i;
		FOR(i,num) G[i].clear();
		FOR(i,num) G[operator[](i)].push_back(i);
	}
};
UF<2020> uf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>A[i]>>B[i]>>C[i]>>D[i];
		A[i]--,C[i]--;
		if(A[i]==C[i]) {
			if(B[i]>=D[i]) {
				cout<<"No"<<endl;
				return;
			}
			i--;
			M--;
			continue;
		}
		
		for(j=A[i];j<B[i];j++) X[i].push_back(j);
		for(j=C[i];j<D[i];j++) Y[i].push_back(j);
		reverse(ALL(X[i]));
		reverse(ALL(Y[i]));
	}
	
	int num=N;
	while(1) {
		
		scc.init(N);
		FOR(i,M) {
			while(X[i].size()&&Y[i].size()&&uf[X[i].back()]==uf[Y[i].back()]) {
				X[i].pop_back();
				Y[i].pop_back();
			}
			if(Y[i].empty()) {
				cout<<"No"<<endl;
				return;
			}
			if(X[i].size()&&Y[i].size()) {
				scc.add_edge(uf[X[i].back()],uf[Y[i].back()]);
			}
		}
		scc.scc();
		if(scc.SC.size()==N) break;
		FORR(sc,scc.SC) {
			num-=sc.size()-1;
			FORR(a,sc) uf(a,sc[0]);
		}
	}
	cout<<"Yes"<<endl;
}

まとめ

うーん、回答にたどり着けず…。