Codeforces #585 Div2 F. Radio Stations

問題設定がややこしい。
https://codeforces.com/contest/1215/problem/F

問題

P個のラジオ基地局のうち、いくつかを選択したい。
その際、以下の条件をすべて満たす選択法はあるか。

• 基地局の対X[i]とY[i]に対し、少なくとも片方は選択されなければならないという条件が複数与えられる。
• 基地局の対U[i]とV[i]に対し、同時に選択することはできないという条件が複数与えられる。
• 各基地局には対応する周波数の区間[L[i],R[i]]が設定されている。選択した基地局では、この区間が共通部分を持たなければならない。

解法

上２つは2-SATで表現できる。
問題は3つ目の種類の条件。
まず、周波数の大小を表現することを考える。
周波数がfである、ということを、2-SATにおいてbool値P[1]～P[f]がTrueでP[f+1]以上がFalseであることで表すとする。
P[x]がFalseでP[x+1]がTrueであってはならないので、各xに対し(P[x] or not P[x+1])を条件に加えればこれは達成できる。

後は基地局yが選択されるなら周波数fが[L[i],R[i]]に収まるという条件は、基地yが選択されることをQ[y]と置くと、
(not Q[y] or P[L[y]]) and (not Q[y] or not P[R[y]+1])
と置くと、全体を2-SATで表現できる。

class SCC {
public:
	static const int MV = 2010000;
	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<MV;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; SC.clear(); SC.resize(MV); NUM.clear();
		assert(NV);
		ZERO(vis); for(int i=0;i<NV;i++) if(!vis[i]) dfs(i);
		ZERO(vis); 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);
	}
};

class TwoSat {
	int NV;
	SCC sc;
public:
	vector<int> val;
	void init(int NV) { this->NV=NV*2; sc.init(NV*2); val.resize(NV);}
	void add_edge(int x,int y) { // k+0:normal k+NV:inverse
		sc.add_edge((x+NV/2)%NV,y);
		sc.add_edge((y+NV/2)%NV,x);
	}
	bool sat() { // empty:false 
		sc.scc();
		for(int i=0;i<NV/2;i++) if(sc.GR[i]==sc.GR[i+NV/2]) return false;
		for(int i=0;i<NV/2;i++) val[i]=sc.GR[i]>sc.GR[i+NV/2];
		return true;
	}
};
TwoSat ts;
int N,P,M,L;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>P>>M>>L;
	ts.init(P+M);
	FOR(i,N) {
		cin>>x>>y;
		ts.add_edge(x-1,y-1);
	}
	FOR(i,P) {
		cin>>x>>y;
		x--;
		ts.add_edge(i+(P+M),x+P);
		if(y<M) ts.add_edge(i+(P+M),y+P+M+P);
	}
	FOR(i,M-1) {
		ts.add_edge(i+P,i+P+1+(P+M));
	}
	FOR(i,L) {
		cin>>x>>y;
		ts.add_edge(x-1+(P+M),y-1+(P+M));
	}
	
	if(!ts.sat()) {
		cout<<-1<<endl;
	}
	else {
		
		int mi=0;
		FOR(i,M) if(ts.val[i+P]) mi=i+1;
		vector<int> R;
		FOR(i,P) if(ts.val[i]) R.push_back(i+1);
		cout<<R.size()<<" "<<mi<<endl;
		FORR(r,R) cout<<r<<" ";
		
	}
}

まとめ

整数値の大小を2-SATで表現するテクはいいな。