TopCoder SRM464 Div1 550

参加はしていない．

概要

n組の中心座標のペアが与えられる．各組の座標を必ずどちらかひとつ使って正方形をn個描く．最小の正方形が最大となるような座標の選び方をしたときの正方形の一辺の長さを求めよ．

解法

2-SAT+2分探索
2-SATはだいぶ前にPKUで，2-SATで解けるらしいという問題を見たけど，実際に書いたことはなく，理解もちゃんとしていなかったのでこれを機にちゃんと解いた．
2-SATはCNFの節の個数が2個のものを解くアルゴリズム．CNFの節をimplicationの形に書き換え，各変数を頂点，implicationを辺とするグラフを作成する．
そしてのような矛盾が生じないかを確認する．この例では，pか~pのどちらかが成田っていなければいけないのに，どちらでも矛盾が生じてしまう．

この問題では，i番目の座標ペアをとすると，piaとpibは同時に成り立ってはいけないので否定の関係にあり，またpiaが成り立つときpjaが成り立たない事をと表せる．この通りにグラフを生成し，矛盾が生じるかどうかを調べればよい．

この問題は頂点の数が少ないためWarshall-Floyd(O(n^3))でも大丈夫．高速化が必要な場合は強連結成分分解を用いてO(n+m)(mは節の個数)でもできる．以下はワーシャルフロイドを用いて実装した．

class ColorfulDecoration {
public:
  vector<int> xa,ya,xb,yb;
  bool check(int mid){
    int n = xa.size(),N=2*n;
    bool graph[N][N];
    memset(graph,false,sizeof(graph));
    REP(i,N)REP(j,N){
      int ii = i/2,jj=j/2;
      if (ii  == jj) continue;
      int x1,y1,x2,y2;
      if (i & 1) x1 = xa[ii],y1 = ya[ii];
      else x1 = xb[ii],y1 = yb[ii];
      if (j & 1) x2 = xa[jj],y2 = ya[jj];
      else x2 = xb[jj],y2 = yb[jj];
      if (abs(x1-x2) < mid && abs(y1-y2) < mid){
        graph[i][j ^ 1] = true;
      }
    }
    REP(i,2*n) graph[i][i] = true;
    REP(k,2*n) REP(i,2*n) REP(j,2*n){
      if (graph[i][k] && graph[k][j])
        graph[i][j] = true;
    }
    bool flag = true;
    for (int i=0;i<2*n;i+=2){
      if (graph[i][i+1] &&
          graph[i+1][i]) flag = false;
    }
    return flag;
  }
  int getMaximum(vector <int> XA, vector <int> YA, vector <int> XB, vector <int> YB) {
    xa = XA;
    xb = XB;
    ya = YA;
    yb = YB;
    int l = 0,h=1000000001;
    while (l < h){
      int mid = (l + h) / 2;
      if (check(mid)){
        l = mid+1;
      }else{
        h = mid;
      }
    }
    return l-1;
  }
}