naoya_t@topcoder

SRM423 Div1 Easy: TheTower

過去問, 練習 | 18:12 |

撃墜された300点問題を解き直してみる。

競技中にsubmitしたコードではx(あるいはy)座標の平均値であたりを付けていたので撃墜されて当然・・・

とりあえず

　x: [ min(x) .. max(x) ]

　y: [ min(y) .. max(y) ]

の範囲にあるのは間違いないので、２重ループで総当たりしてみれば簡単なケースについては問題なく求められる。

#include <vector>
#include <algorithm>
using namespace std;

#define all(x)  (x).begin(),(x).end()

class TheTower {
public:
  vector<int> count(vector<int> x, vector<int> y) {
    int n = x.size();
    int xmin = *min_element(all(x)), xmax = *max_element(all(x)),
        ymin = *min_element(all(y)), ymax = *max_element(all(y));
    vector<int> m(n,INT_MAX); m[0] = 0;
    for (int x_=xmin; x_<=xmax; x_++) {
      for (int y_=ymin; y_<=ymax; y_++) {
        vector<int> d(n);
        for (int i=0;i<n;i++) d[i] = abs(x_ - x[i]) + abs(y_ - y[i]);
        sort(all(d));
        int a = d[0];
        for (int i=1;i<n;i++) {
          a += d[i];
          if (a < m[i]) m[i] = a;
        }
      }
    }
    return m;
  }
};

しかし x, y の値域はそれぞれ[1,1000000]なので、xmax - xmin と ymax - ymin が大きい場合にTLE。

ここで

　f(x,y) = Σ|x - xi| + Σ|y - yi|

が最小値をとるのは

　g(x) = Σ|x - xi|

　h(y) + Σ|y - yi|

がそれぞれ最小になる範囲である。それぞれが最小値をとるのは１点もしくは２点間の区間なので、その中に少なくとも１つの点(xj, yj)が含まれる。

従って、x,y座標とも、checkerのある座標のみ（各最大50）を調べればよく、

#include <vector>
#include <algorithm>
using namespace std;

#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define all(x)  (x).begin(),(x).end()

class TheTower {
public:
  vector<int> count(vector<int> x, vector<int> y) {
    int n = x.size();
    vector<int> xs(all(x)); sort(all(xs));
    vector<int> ys(all(y)); sort(all(ys));
    vector<int> m(n,INT_MAX); m[0] = 0;
    tr(xs,x_) {
      tr(ys,y_) {
        vector<int> d(n);
        for (int i=0;i<n;i++) d[i] = abs(*x_ - x[i]) + abs(*y_ - y[i]);
        sort(all(d));
        int a = d[0];
        for (int i=1;i<n;i++) {
          a += d[i];
          if (a < m[i]) m[i] = a;
        }
      }
    }
    return m;
  }
};

O(n^3)だけどn≦50なのですぐに終わる。

追記

nitoyonさんの解説とは考える順番が逆かな。