SRM613 Div2Med TaroFriends

問題概要
数直線上にいる複数の猫が、それぞれの与えられた初期位置から絶対値Xだけ移動する。猫が最適な動き方をしたとき、猫のいる区間の中で最も端にいる２匹の距離を最小化せよ。

解法
どの２匹が区間の端になるかを二重ループで決める。このときすべての猫が２匹によってつくられる区間上に入り込むことができるかを判定する。すべての猫を絶対値Xだけ移動させて 2*N の配列に入れたものを使って端の２匹を決めればよい。
以下、writer解と同じアルゴリズム。１匹を区間の端として２度使うのをはじく場合分けが不必要なことが証明できない。

class TaroFriends {
public:
  int getNumber(vector <int> coordinates, int X) {
    int const N = coordinates.size();
    
    int *all = new int[N*2];
    for(int i=0; i<N; i++) {
      all[i*2]   = coordinates[i] - X;
      all[i*2+1] = coordinates[i] + X;
    }
    
    sort(all, all+N*2);
    
    int res = (int)1e9;
    for(int i=0; i<N*2; i++) {
      for(int j=0; j<=i; j++) {
	bool ok = 1;
	for(int k=0; k<N; k++) {
	  bool b1 = (all[j] <= coordinates[k] - X) && (coordinates[k] - X <= all[i]);
	  bool b2 = (all[j] <= coordinates[k] + X) && (coordinates[k] + X <= all[i]);
	  if(b1 == b2 && b2 == 0) {
	    ok = 0;
	    break;
	  }
	}
	if(ok) {
	  res = min(res, all[i] - all[j]);
	}
      }
    }
    return res;
  }
};