SRM 464 500pt: ColorfulDecoration

TopCoder

問題概要

(xa[i], ya[i])か(xb[i], yb[i])を中心とする互いに交わらないような正方形の大きさの最小値を最大化する問題。N<50、0<=xa[i], ya[i], xb[i], yb[i] <= 10^9。

考えたこと

  • (当時は全然分からなかったけど2-SATという単語が終了後Twitterなどで飛び交っていてなんじゃそりゃと思った記憶がある)
  • この問題二分探索+2-SATで解くって知ってたから2-SATに落とせたけど自力で思いつくのは難しそう。
    • もっとも、二分探索は流石に気付きそう。最小値の最大化という分かりやすい形だし。
  • !(x && y)を見てすぐに(!x || !y)に変形するなんて普通は思いつきそうにない。
  • 解法知ってるんだから後は実装するだけなんだけど、2-SATを思い出す意味で強連結成分分解からスクラッチで書く。
  • サンプルの最後が合わない。何かと思ったら上限が足りてない。
  • 基本的にintのINFは2倍してもオーバーフローしないように2^29としているんだけど、これじゃ足りない。
  • 上限を2^30にするとぎりぎり大丈夫だけど色々不安なのでぎりぎりのところにしておく。
    • (low + high) / 2の分子がオーバーフローしないようにするテクニックがあるのは知ってるけど。
  • 修正。無事通った。

practiceで通ったコード

計算量O(log X * N^2)。

#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_N = 50;
const int MAX_V = 2 * MAX_N;

int N;
int V;
vector<int> graph[MAX_V];
vector<int> rev_graph[MAX_V];
bool visited[MAX_V];
int cmp[MAX_V];
vector<int> st;

struct ColorfulDecoration {

	int getMaximum(vector <int> xa, vector <int> ya, vector <int> xb, vector <int> yb) {
		//解空間[low, high)の二分探索
		int low = 0, high = 1000000000+1;

		while(high - low > 1){
			int mid = (low + high) / 2;
			if(check(xa, ya, xb, yb, mid)){
				low = mid;
			}
			else{
				high = mid;
			}
		}

		return low;
	}

	bool check(const vector<int>& xa, const vector<int>& ya, const vector<int>& xb, const vector<int>& yb, int r){
		N = xa.size();
		V = 2 * N;

		//初期化
		clear_graph();

		//a - bのダメな組み合わせを列挙する
		//A - A型
		for(int i=0; i<N; i++){
			for(int j=i+1; j<N; j++){
				if(is_intersect(xa[i], ya[i], xa[j], ya[j], r)){
					add_edge(i, j);
				}
			}
		}

		//A - B型
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++)if( i != j ){
				if(is_intersect(xa[i], ya[i], xb[j], yb[j], r)){
					add_edge(i, j+N);
				}
			}
		}


		//B - A型
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++)if( i != j ){
				if(is_intersect(xb[i], yb[i], xa[j], ya[j], r)){
					add_edge(i+N, j);
				}
			}
		}

		//B - B型
		for(int i=0; i<N; i++){
			for(int j=i+1; j<N; j++){
				if(is_intersect(xb[i], yb[i], xb[j], yb[j], r)){
					add_edge(i+N, j+N);
				}
			}
		}

		return solve_2SAT();
	}

	void clear_graph(){
		for(int i=0; i<MAX_V; i++){
			graph[i].clear();
			rev_graph[i].clear();
		}

	}

	//否定形を求める
	int get_not(int x){
		return x + (x < N ? N : -N);
	}

	//aかつbはダメ、という条件を与える
	//!(a && b) == (!a || !b) == (a ⇒ !b) && (b ⇒ !a)
	void add_edge(int a, int b){
		graph[a].push_back( get_not(b) );
		graph[b].push_back( get_not(a) );
		rev_graph[get_not(b)].push_back(a);
		rev_graph[get_not(a)].push_back(b);
	}

	//交わるかどうかの判定
	bool is_intersect(int x0, int y0, int x1, int y1, int r){
		return abs(x0 - x1) < r && abs(y0 - y1) < r;
	}

	//2_SATを解く
	bool solve_2SAT(){

		//強連結成分分解する
		SCC();

		bool ans = true;
		//aかつ!aが同じ連結成分の中にないか
		for(int i=0; i<N; i++){
			ans &= (cmp[i] != cmp[i+N]);
		}

		return ans;
	}

	void SCC(){

		//初期化
		memset(visited, 0, sizeof(visited));
		memset(cmp, 0, sizeof(cmp));
		st.clear();

		for(int i=0; i<V; i++)if(!visited[i]){
			dfs(i);
		}

		memset(visited, 0, sizeof(visited));
		int cnt = 0;
		while(!st.empty()){
			int v = st.back(); st.pop_back();
			if(!visited[v]){
				rev_dfs(v, cnt++);
			}
		}
	}

	void dfs(int v){
		visited[v] = true;
		for(int i=0; i<(int)graph[v].size(); i++){
			int u = graph[v][i];
			if(!visited[u]){
				dfs(u);
			}
		}
		st.push_back(v);
	}

	void rev_dfs(int v, int cnt){
		visited[v] = true;
		for(int i=0; i<(int)rev_graph[v].size(); i++){
			int u = rev_graph[v][i];
			if(!visited[u]){
				rev_dfs(u, cnt);
			}
		}
		cmp[v] = cnt;
	}
};