Hatena::Grouptopcoder

cou929のTopCoder日記

2009-05-16

SRM421 div2

09:43

Easy - GymTraining

ジムでトレーニングを胃している。トレーニング回数のノルマが与えられる。また、ある回数トレーニングして、pulseがたまると、トレーニングを休まなければならない。ノルマを達成するために最低限必要な時間を求める。

250にしては、少し時間がかかってしまいました。特に、pulseの上限値は超えてはならず、下限値は超えても良いという条件を勘違いしていたため、時間を取られました。

class GymTraining {
public:
  int trainingTime(int needToTrain, int minPulse, int maxPulse, int trainChange, int restChange)
  {
    int pulse = maxPulse - minPulse;
    int now = 0;
    int ret = 0;
    int trained = 0;

    if (pulse < trainChange)
      return -1;

    while (trained < needToTrain)
      {
	ret++;
	if (now + trainChange <= pulse)
	  {
	    now += trainChange;
	    trained++;
	  }
	else
	  {
	    now = min(now - restChange, 0);
	  }
      }
    return ret;
  }
};

Medium - EquilibriumPoints

物体の位置と質量のセットが与えられる。全てのEquilibrium Pointの位置を求めよ。

連立方程式を解く方法がわからず、Editorialを見ながら解きました。連立方程式の解は、バイナリサーチで見つけるそうです。なるほど、この手法は今後も応用する機会がありそうです。また、バイナリサーチのチュートリアルも良い記事でした。あとで練習問題にチャレンジします。

class EquilibriumPoints {
public:
  vector <int> x;
  vector <int> m;

  double calc(double d)
  {
    double ret = 0;

    for (int i=0; i<x.size(); i++)
      {
	if (x[i] < d)
	  ret -= m[i] / (d - x[i]) / (d - x[i]);
	else
	  ret += m[i] / (x[i] - d) / (x[i] - d);
      }

    return ret;
  }

  double bs(int left, int right)
  {
    double d = 0, l = left, r = right;
    int i = 0;

    while (i++ < 500)
      {
	d = (l + r) / 2.0;
	double res = calc(d);

	if (res == 0)
	  break;
	else if (res < 0)
	  l = d;
	else if (0 < res)
	  r = d;
      }

    return d;
  }

  vector <double> getPoints(vector <int> _x, vector <int> _m)
  {
    x = _x;
    m = _m;
    vector <double> ret;

    for (int i=0; i<x.size()-1; i++)
      ret.push_back(bs(x[i], x[i+1]));

    return ret;
  }
};

Hard - FloorIndicator

一部が壊れているかもしれないインジケータがある。表示している可能性のある数字の平均を求める。

時間がかかりましたが、一応実装はできました。まず各数値について、可能性のある数字を調べていきます。その後、全ての組み合わせを再帰的に調べていき、平均を求めます。

class FloorIndicator {
public:
  int toInt(string s) {int r = 0; istringstream ss(s); ss >> r; return r;}
  string toStr(int n) {ostringstream ss; ss << n; return ss.str();}
  double averageFloor(int N, vector <string> indicator)
  {
    vector <string> nums;
    string s = "###...#.###.###.#.#.###.###.###.###.###";
    nums.push_back(s);
    s = "#.#...#...#...#.#.#.#...#.....#.#.#.#.#";
    nums.push_back(s);
    s = "#.#...#.###.###.###.###.###...#.###.###";
    nums.push_back(s);
    s = "#.#...#.#.....#...#...#.#.#...#.#.#...#";
    nums.push_back(s);
    s = "###...#.###.###...#.###.###...#.###.###";
    nums.push_back(s);

    vector <vector <int> > vals;

    for (int i=0; i<N; i++)
      {
	bool candidates[10];
	memset(candidates, true, sizeof(candidates));

	for (int j=0; j<10; j++)
	  for (int col=0; col<5; col++)
	    for (int row=0; row<3; row++)
	      if (indicator[col][row + i*4] == '#' && nums[col][row + j*4] == '.')
		candidates[j] = false;

	vector <int> t;
	for (int k=0; k<10; k++)
	  if (candidates[k])
	    t.push_back(k);

	if (t.empty())
	  return -1;
	
	vals.push_back(t);
      }

    double nume = 0;
    double deno = 0;
    queue <string> q;
    for (int i=0; i<vals[0].size(); i++)
      q.push(toStr(vals[0][i]));

    while (!q.empty())
      {
    	string cur = q.front();
    	q.pop();

    	if (cur.size() == N)
    	  {
    	    nume += (double)toInt(cur);
    	    deno += 1.0;
    	    continue;
    	  }

    	for (int i=0; i<vals[cur.size()].size(); i++)
    	  q.push(cur + toStr(vals[cur.size()][i]));
      }

    return nume / deno;
  }
};

しかしこの解法では、大きな値の際にTLEでした。Editorialによると、各桁ごとに平均を計算し、足し込んでいくという方法が紹介されていました。これには関心しました。

class FloorIndicator {
public:
  double averageFloor(int N, vector <string> indicator)
  {
    string nums[] = {"###...#.###.###.#.#.###.###.###.###.###",
		     "#.#...#...#...#.#.#.#...#.....#.#.#.#.#",
		     "#.#...#.###.###.###.###.###...#.###.###",
		     "#.#...#.#.....#...#...#.#.#...#.#.#...#",
		     "###...#.###.###...#.###.###...#.###.###"};

    double ret = 0;

    for (int i=0; i<N; i++)
      {
	bool candidates[10];
	memset(candidates, true, sizeof(candidates));

	for (int j=0; j<10; j++)
	  for (int col=0; col<5; col++)
	    for (int row=0; row<3; row++)
	      if (indicator[col][row + i*4] == '#' && nums[col][row + j*4] == '.')
		candidates[j] = false;

	int sum = 0;
	int total = 0;
	for (int k=0; k<10; k++)
	  if (candidates[k])
	    {
	      sum += k;
	      total++;
	    }

	if (total == 0)
	  return -1;

	ret = ret * 10 + (double)sum / total;
      }

    return ret;
  }
};