読者です 読者をやめる 読者になる 読者になる

SRM613 Div2Med TaroFriends

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

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

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;
  }
};