WUPC 2019 : D - Choose Your Characters

ちょっと手間取ったけどどうにかなった。
https://atcoder.jp/contests/wupc2019/tasks/wupc2019_d

問題

N人の人がいる。
２人のペアa,bの間には以下のいずれかの関係がなりたつ。

• 互いに有利でも不利でもない。
• 片方が片方に有利であり、反対派は逆に不利である。

有利不利の関係M個が与えられる。
N人の人のうちある連続区間[L,R]のうち、N人の誰に対しても、[L,R]のうちだれか１人は不利でない人が存在するような最短区間をこたえよ。

解法

左端Lを総当たりし、対応する右端Rを求めよう。
L番の人にとって不利な人が何人かいるとして、それぞれに対し、不利でない人が現れる最小の人の番号を求め、その最大値を解としよう。
ある人に対し不利である人が連続すると、愚直に処理するとO(N^2)かかりかねない。
よって、「ある人に対し、ある番号以降で初めて不利でなくなる人の番号」のsetをlower_boundで探すと高速化できる。

int N,M;
set<int> W[101010],L[101010],NF[101010];
int R[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		W[x].insert(y);
		L[y].insert(x);
	}
	FOR(i,N) W[i+1].insert(i+1),L[i+1].insert(i+1);
	for(i=1;i<=N;i++) {
		int cur=0;
		while(1) {
			auto it=W[i].lower_bound(cur);
			if(it==W[i].end()) break;
			cur=*it;
			while(W[i].count(cur)) cur++;
			NF[i].insert(cur);
		}
		
	}
	
	int A=0,B=1<<30;
	for(i=1;i<=N;i++) {
		R[i]=i+1;
		FORR(l,L[i]) {
			R[i]=max(R[i],*NF[l].lower_bound(i));
		}
		if(R[i]<=N && R[i]-i<B-A) A=i,B=R[i];
	}
	if(B==1<<30) {
		cout<<-1<<endl;
	}
	else {
		cout<<A<<" "<<B<<endl;
	}
}

まとめ

コードはともかく、若干説明しにくいな。