Hatena::Grouptopcoder

cou929のTopCoder日記

2009-05-29

SRM423 div2

16:10

Easy - TheSimpleGame

n x n の盤上で、全ての駒を4角のどこかに移動させるには、最短で何手かかるか。駒の移動は一手で上下左右に1マス移動できる。

与えられたそれぞれの駒の初期位置から、4角すべてにかかる手数を調べ、その中から最小値を選択していきます。

class TheSimpleGame {
public:
  int count(int n, vector <int> x, vector <int> y)
  {
    int ret = 0;
    int corners[4][2] = {{1, 1}, {1, n}, {n, 1}, {n, n}};

    for (int i=0; i<x.size(); i++)
      {
	int t = n*n;
	for (int j=0; j<4; j++)
	  {
	    int tmp = abs(corners[j][0] - x[i]);
	    tmp += abs(corners[j][1] - y[i]);
	    t = min(t, tmp);
	  }
	ret += t;
      }

    return ret;
  }
};

Medium - TheTower

上の問題と同様の条件(ただし盤の広さが無限)を考える。N個の駒の初期位置が与えられた場合、1からN個の駒が同じ位置に集まる際に必要な最短の手数を、それぞれ求める。

わからなかったので、editorialを参考に解きました。ポイントは全ての2駒間の距離を調べ、昇順にソートするところです。ソートの結果を1つずつ足していくことで、その駒を起点とした0からNまでの最小の手数を求められます。

class TheTower {
public:
  vector <int> count(vector <int> x, vector <int> y)
  {
    vector <int> ret;

    for (int i=0; i<x.size(); i++)
      ret.push_back(1000000000);

    for (int i=0; i<x.size(); i++)
      for (int j=0; j<y.size(); j++)
	{
	  vector <int> dists;
	  for (int k=0; k<x.size(); k++)
	    dists.push_back(abs(x[i] - x[k]) + abs(y[j] - y[k]));

	  sort(dists.begin(), dists.end());

	  int sum = 0;
	  for (int k=0; k<x.size(); k++)
	    {
	      sum += dists[k];
	      ret[k] = min(ret[k], sum);
	    }
	}

    return ret;
  }
};