ちょっと手間取ったけどどうにかなった。
https://atcoder.jp/contests/wupc2019/tasks/wupc2019_d
問題
N人の人がいる。
2人のペアa,bの間には以下のいずれかの関係がなりたつ。
- 互いに有利でも不利でもない。
- 片方が片方に有利であり、反対派は逆に不利である。
有利不利の関係M個が与えられる。
N人の人のうちある連続区間[L,R]のうち、N人の誰に対しても、[L,R]のうちだれか1人は不利でない人が存在するような最短区間をこたえよ。
解法
左端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; } }
まとめ
コードはともかく、若干説明しにくいな。