SRM423 Div2 600

問題

N個のチェッカーが無限に大きいボードにおいてある。それぞれのx,y座標が与えられる時、i個のチェッカーが同じマスになるために必要な移動数をそれぞれで計算し配列を返す。チェッカーは1回に縦横方向に1マス動くことができる。

考え方

ありえる各点をすべて調べるのは10^12なので、無理。
かといって、2次元なので、すでにあるチェッカーのところに集まるわけではない(Example1)。

ある点(x,y)に集まることを考えると、その点と各チェッカーの距離が近いものからi個(近い順にならんだx,yをx',y'とする)その点に移動する移動距離は、(|x-x'[1]|+...+|x-x'[i]|)+(|y-y'[1]|+...+|y-y'[i]|)となる(これはx,y軸がそれぞれ独立していることもわかる)。
各|x-x'[1]|+...+|x-x'[i]|を最小化するxは、x'[1]からx'[i]のうちのどれかになる(メジアンの性質的にも)。実際はそれ以外の間の点も成り立つが、点自体も成り立つ(重要)。
各x,yはそれぞれ50個ずつなので、すべてのx,yの組み合わせ50*50の点(x,y)について、その点から与えられた点(x[i],y[i])との(マンハッタン)距離を求めて近い距離からk個近づいた時の値の最小値を保存していく。

class TheTower {
public:
  vector <int> count(vector <int> x, vector <int> y) {
    int N = x.size();
    vector<int> X=x, Y=y, ret; rep(i,N) ret.push_back(1000000000);
    ret[0] = 0;
    sort(ALLOF(X));
    sort(ALLOF(Y));
    rep(i,N) rep(j,N){ //すべての点の組み合わせについて
      int tx = x[i], ty = y[j];
      vector<int> dist;
      rep(k,N){
        dist.push_back(abs(x[k]-tx)+abs(y[k]-ty)); //各点への距離を求める
      }
      sort(ALLOF(dist));//距離の近い順に並べる
      int sum = 0;
      REP(k,0,N){
        sum += dist[k];
        ret[k] = min(ret[k], sum); //近いものからk個分重なった場合の最小移動数
      }
    }
    return ret;
  }
};

反省

探索区間を減らすことを考える。
条件から調べる範囲は特定的にならないといけないことにも気づけるはず。
サンプルに惑わされない。