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