SRM 613 DIV1 Easy - TaroFriends (復習○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13005&rd=15846
・猫が一直線上に数匹存在する。
・それぞれの猫が１度移動し、その移動する距離はDであることがわかっている。
・ただし、左側もしくは右側のどちらに移動するかはわかっていない。
・移動した後に、最も左端と右端の猫の距離が最短になるときの値を求める。
解き方
・とりあえずソートして考えるのがよさそう
・左端と右端は右と左に動けばよい？
・左と右をポイントし、そのうち差の距離が小さくなる方を採用していけばよいか
・サンプルは通った
→System Failed
・貪欲法で解こうとしたが、ソートしたのちに左に動く集合と、右に動く集合にわける場合の数は最大５１通りなので全探索できる。
・なんとなく思いついたが、貪欲法の方を実装してしまった。
・反省：トレースして思いついた貪欲法を実装してしまったが、今回のようにソートした後に全探索が可能なケースがあるので全探索の線を優先して考える。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class TaroFriends {
public: int getNumber(vector<int> coordinates, int X) {
int n=coordinates.size();
sort(all(coordinates));
long long ret=1e+18;
FORE(i,0,n+1){
vector<int> vx;
FORE(j,0,i)vx.push_back(coordinates[j]+X);
FORE(j,i,n)vx.push_back(coordinates[j]-X);
sort(all(vx));
ret=min(ret,(long long)vx[n-1]-vx[0]);
}
return (int)ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class TaroFriends {
public: int getNumber(vector<int> coordinates, int X) {
int n=coordinates.size();
sort(all(coordinates));
long long ret=1e+18;
FORE(i,0,n+1){
vector<int> vx;
FORE(j,0,i)vx.push_back(coordinates[j]+X);
FORE(j,i,n)vx.push_back(coordinates[j]-X);
sort(all(vx));
ret=min(ret,(long long)vx[n-1]-vx[0]);
}
return (int)ret;
}
};
