SRM 651 div1 med: FoxConnection3

一つ一つのロジックは単純だけど、ぱっと見では全く方針が立たなかった。

問題:abs(x), abs(y) <= 10^9 の2次元平面に1〜6匹の狐がいる。これらすべてが少なくとも1匹と隣接するように移動する時、移動量の合計を最小化せよ。

解法:全探索する。具体的には、
①n匹の狐がどのような形をとることがあり得るかを調べる(createShapeのところ)
②それぞれの形について、狐の総移動量が最小になるようにする。最小の移動量の求め方を説明する。
形が{(sx[0], sy[0]), (sx[1], sy[1]),...}となっていたとすると、結局狐が集まる座標は、ある定数Ox, Oyを用いて{(sx[0]+Ox, sy[0]+Oy), (sx[0]+Ox, sy[1]+Oy), ...}と表せる。よって、最初狐が{(x[0], y[0]), (x[1], y[1]), ...}にいたとすると、移動量は|x[0]-(sx[0]+Ox)| + |x[1]-(sx[1]+Ox)| + ... + |y[0]-(sy[0]+Oy)| + |y[1]-(sy[1]+Oy)| + ...となる。これはx座標についての式|x[0]-(sx[0]+Ox)| + |x[1]-(sx[1]+Ox)| + ...と、y座標についての式|y[0]-(sy[0]+Oy)| + |y[1]-(sy[1]+Oy)| + ...に分けて考えることができ、例えばx座標について最小化する候補はx[0]-sx[0],x[1]-sx[1],...である(式は|Ox-(x[0]-sx[0])| + |Ox-(x[1]-sx[1])| + ...となるが、このように|x-d0| + |x-d1| +...となっている式はx=d0, x = d1, ...が最小化する解の候補)。よって、これらをすべて試せば良い。
①については、計算量を減らすためにseenという関数を使って工夫している。
以下ソースコード

typedef long long ll;
typedef pair<int, int> P;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const ll INF = 1ll<<60;
#define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin();itr!=c.end();itr++)

vector<vector<P> > shape;
vector<int> X, Y;
set<vector<P> > S;

bool seen(const vector<P>& vs) {
    int xmin = 10, ymin = 10;
    int n = vs.size();
    for (int i = 0; i < n; i++) {
        xmin = min(xmin, vs[i].first);
        ymin = min(ymin, vs[i].second);
    }
    vector<P> nvs;
    for (int i = 0; i < n; i++) {
        nvs.push_back(P(vs[i].first-xmin, vs[i].second-ymin));
    }
    sort(nvs.begin(), nvs.end());
    if (S.find(nvs) != S.end()) return true;
    else {
        S.insert(nvs);
        return false;
    }
}

void createShape(int n, int cur, vector<P>& path) {
    if (cur == n) {
        seen(path);
        return;
    }
    if (seen(path)) return;
    int m = path.size();
    for (int i = 0; i < m; i++) {
        P now = path[i];
        for (int k = 0; k < 4; k++) {
            P next = P(now.first+dx[k], now.second+dy[k]);
            if (find(path.begin(), path.end(), next) != path.end()) continue;
            path.push_back(next);
            createShape(n, cur+1, path);
            path.pop_back();
        }
    }
}

ll getDist(int n, int index) {
    vector<int> perm(n);
    for (int i = 0; i < n; i++) perm[i] = i;
    ll ret = INF;
    do {
        vector<ll> xs, ys;
        for (int i = 0; i < n; i++) {
            xs.push_back(X[perm[i]]-shape[index][i].first);
            ys.push_back(Y[perm[i]]-shape[index][i].second);
        }
        ll xmin = INF, ymin = INF;
        for (int i = 0; i < n; i++) {
            ll xsum = 0, ysum = 0;
            for (int j = 0; j < n; j++) {
                xsum += abs(xs[j]-xs[i]);
                ysum += abs(ys[j]-ys[i]);
            }
            xmin = min(xsum, xmin);
            ymin = min(ysum, ymin);
        }
        ret = min(ret, xmin+ymin);
    } while (next_permutation(perm.begin(), perm.end()));
    return ret;
}

class FoxConnection3 {
public:
    long long minimalSteps(vector <int> x, vector <int> y) {
        X = x; Y = y;
        int n = x.size();
        vector<P> path;
        path.push_back(P(0, 0));
        S.clear();
        shape.clear();
        createShape(n, 1, path);
        for (auto el : S) {
            if (el.size() == n) {
                shape.push_back(el);
            }
        }
        int m = shape.size();
        cout << m << endl;
        cout << S.size() << endl;
        ll ret = INF;
        for (int i = 0; i < m; i++) {
            ret = min(ret, getDist(n, i));
        }
        return ret;
    }
};