TopCoder SRM 613 Div1 Easy TaroFriends [1人競技プログラミング Advent Calendar 2016 13日目]

この記事は1人競技プログラミング Advent Calendar 2016 13日目の記事です。

問題概要：
TopCoder Statistics - Problem Statement
猫がN匹存在し、i番目の猫はx座標がcoordinates[i]の位置にいる。
全ての猫は、それぞれの位置から正の方向か負の方向にX(0<=X<=100,000,000)歩分移動させる必要がある。
両端の猫の位置が最も近くなるように移動した際の両端の猫の距離を求めよ。

解いた方法：
最初に猫の座標でソートする。
全ての猫が同じ座標でなければ、お互い中心に向かうように移動するのが最も猫の距離が近くなる。
ソート後折り返す位置を探索し、一番近い距離を探索すると解が出てくる。

#include<bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

class TaroFriends {
    public:
    vector<int> coordinates;
    int X;
    int getNumber(vector<int> _coordinates, int _XX) {
        coordinates = _coordinates, X = _XX;

        sort(ALL(coordinates));
        int result = 2000000000;
        REP(i, coordinates.size()){
            int min_x = INF;
            int max_x = -INF;

            REP(j, i){
                int tmp = coordinates[j] + X;
                min_x = min(min_x, tmp);
                max_x = max(max_x, tmp);
            }
            REP2(j, i, coordinates.size()){
                int tmp = coordinates[j] - X;
                min_x = min(min_x, tmp);
                max_x = max(max_x, tmp);
            }

            result = min(result, max_x - min_x);
        }
        return result;
    }
};