kmjp's blog

競技プログラミング参加記です

AtCoder ARC #069 : F - Flags

ARC

シンプルな問題設定ながら、勉強になりました。
http://arc069.contest.atcoder.jp/tasks/arc069_d

問題

一次元の数直線上に、N個の旗を立てる。
各旗は、座標X[i]かY[i]のいずれか片方に立てるものとする。
この時、任意の2つの旗の間の距離の最小値dをできるだけ大きくしたい。
dの最大値を求めよ。

解法

題意より、dを二分探索するのはすぐに思いつく。

まずは、計算量を無視して簡単な考え方をしてみる。
N個の真偽値を取る変数A[i]を考える。
A[i]=Trueならi番目の旗をX[i]、FalseならY[i]に立てることに相当させてみる。
2つの旗u,vの距離がd未満になってはいけないので、2つの旗を総当たりすることで、A[u]とA[v]の間に条件が生じる場合がある。
つまり2変数の間に関する条件が複数登場するので、2-SATとみなすことができる。
これは解けるには解けるのだが、辺の数がO(N^2)となるため、二分探索の手間も考えると座標の最大値をZとして計算量がO(N^2*Z)となりTLに間に合わない。

そこで2-SATから(2-SATを強連結成分分解に持ち込むために)生成される有向グラフに登場する辺を減らすことを考える。
まず変数のとり方を変える。
旗iに真偽値変数を2つずつとる。こうすると2N個の変数が登場し、2-SATを解くためには4N個の頂点が登場することになる。

  • B[i] := i番の旗をX[i]に立てるかどうか
  • C[i] := i番の旗をY[i]に立てるかどうか

各旗iはX[i]かY[i]か片方は立てないといけないので、まずグラフ中に(￢B[i]⇒C[i])と(￢C[i]⇒B[i])に相当する辺を張る。
これらはO(N)本にとどまるので問題ない。

問題は距離d未満に他の旗がないことである。
たとえば今旗をX[i]に立てる場合、(X[i]-(d-1))～(X[i]+(d-1))の範囲内の座標に相当する変数D[x] (D[x]はB[j]かC[j])は同時に成り立たないので(B[i]⇒￢D[x])の辺を張らなければならない。
問題は、対象のD[x]がO(N)個あるのでこのままだと結局辺がO(N^2)本になることである。

ここで、上記辺を張るべきD[x]に相当する座標の区間は、一次元座標軸における連続区間であることを考える。
よってSegTreeの要領で、「ここに辺を張れば結局ある[￢D[x],￢D[x+(2^h)])個の頂点をカバーできる」というような頂点を作ろう。

もう少し具体的には以下の頂点V(h,k)を作っておくと、(B[i]⇒V(h,k))の辺を張ることは、(B[i]⇒D[k*(2^h)])～(B[i]⇒D[(k+1)*(2^h)-1])の2^h個の辺を張るのと等しいとみなせるようになる。

  • h＞0の場合、V(h,k)からはV(h-1,2*k)とV(h-1,2*k+1)に辺を張る。
  • h=0の場合、V(0,k)は￢D[k]に対応する点そのもの。

その場合、B[i]・C[i]に対し、対象となる￢D[x]の全頂点に1つ1つ辺を張る必要はなく、辺の数はO(logN)に抑えることができる。

class SCC {
public:
	static const int MV = 1<<17;
	vector<vector<int> > SC; int NV,GR[MV],rev[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;  rev[cu]=ind;
		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();
		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]]){
			revdfs(NUM[i],c);  c++;
		}
	}
};

int N;
int X[101010],Y[101010];
int id[101010][2];
int mi;
vector<pair<int,int>> E;

SCC sc;
void add(int c,int x,int y,int l=0,int r=1<<16,int k=1) { // x<=i<y
	if(x>=y) return;
	if(r<=x || y<=l) return;
	if(x<=l && r<=y) {
		sc.add_edge(c,k);
	}
	else {
		add(c,x,y,l,(l+r)/2,k*2);
		add(c,x,y,(l+r)/2,r,k*2+1);
	}
}

int ok(int v) {
	int i,j;
	int A=1<<16, B=1<<15;
	sc.init(1<<17);
	v--;
	for(i=2;i<1<<16;i++) {
		sc.add_edge(i,i*2);
		sc.add_edge(i,i*2+1);
	}
	
	FOR(i,N) {
		sc.add_edge(A+id[i][0]+B,A+id[i][1]);
		sc.add_edge(A+id[i][1]+B,A+id[i][0]);
		
		int x=lower_bound(ALL(E),make_pair(X[i]-v,0))-E.begin();
		int y=lower_bound(ALL(E),make_pair(X[i]+v+1,0))-E.begin();
		add(A+id[i][0],x+B,id[i][0]+B);
		add(A+id[i][0],id[i][0]+1+B,y+B);
		x=lower_bound(ALL(E),make_pair(Y[i]-v,0))-E.begin();
		y=lower_bound(ALL(E),make_pair(Y[i]+v+1,0))-E.begin();
		add(A+id[i][1],x+B,id[i][1]+B);
		add(A+id[i][1],id[i][1]+1+B,y+B);
	}
	sc.scc();
	FOR(i,B) if(sc.GR[A+i]==sc.GR[A+i+B]) return 0;
	return 1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		if(X[i]>Y[i]) swap(X[i],Y[i]);
		E.push_back({X[i],i});
		E.push_back({Y[i],i+(1<<14)});
	}
	sort(ALL(E));
	FOR(i,N) {
		id[i][0]=lower_bound(ALL(E),make_pair(X[i],i))-E.begin();
		id[i][1]=lower_bound(ALL(E),make_pair(Y[i],i+(1<<14)))-E.begin();
	}
	
	
	int ret=0;
	for(i=29;i>=0;i--) if(ok(ret+(1<<i))) ret+=1<<i;
	cout<<ret<<endl;
}

まとめ

なんかしら辺をまとめるんだろうなと思ったけど、こういう方法があるのね。