Hatena::Grouptopcoder

cou929のTopCoder日記

2009-05-12

SRM440 div2

23:38

Easyはなぜか解法が思いつかず、解けなかった。Mediumは時間が足りず、こちらも解けなかった。結果レーティングがまた100くらい落ちた。

Easy - IncredibleMachineEasy

重力加速度を求める問題。落ち着いて数式を展開すれば解けるはずだが、計算途中で加速度の項の分子と分母を間違えていて、解けなかった。

class IncredibleMachineEasy {
public:
  double gravitationalAcceleration(vector <int> height, int T)
  {
    double d = 0;
    for (int i=0; i<height.size(); i++)
      d += sqrt(height[i] * 2);

    return  d*d / (double)(T*T);
  }
};

Medium - MazeWanderingEasy

ひらめき系ではなく、愚直に組めば解ける問題。次に進む座標と、現在までに何回decisionがあったかを保存しながら、再帰的に探索すればできる。Easyでねばりすぎた & 解いてる途中でNHKの集金が来たため、時間が足りず間に合わなかった。

同じ部屋のシステムテストで落ちていた人は、以下の理由で落ちていた。

  • 現在の座標の周囲をしらべる際、値の範囲(0以上maze.size()以下など)を考慮していない。
  • 次に進めるセルがない場合を考慮していない。

また、問題文が無駄に長く、苦労しました。クラシック音楽のくだりはいらないと思います。

class MazeWanderingEasy {
public:
  int decisions(vector <string> maze)
  {
    bool visited[maze.size()][maze[0].size()];
    memset(visited, false, sizeof(visited));
    queue <vector <int> > q;
    vector <int> start;
    int ret;
    int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    for (int i=0; i<maze.size(); i++)
      for (int j=0; j<maze[0].size(); j++)
	if (maze[i][j] == 'M')
	  {
	    start.push_back(i);
	    start.push_back(j);
	  }

    start.push_back(0);
    q.push(start);

    while (!q.empty())
      {
	vector <int> here;
	here = q.front();
	q.pop();

	int x = here[0];
	int y = here[1];

	if (maze[x][y] == '*')
	  {
	    ret = here[2];
	    break;
	  }

	visited[x][y] = true;

	int c = 0;
	int d = 0;

	for (int i=0; i<4; i++)
	  {
	    int cx = x + dir[i][0];
	    int cy = y + dir[i][1];
	    if (0 <= cx && cx < maze.size() && 0 <= cy && cy < maze[0].size())
	      if (!visited[cx][cy] && (maze[cx][cy] == '.' || maze[cx][cy] == '*'))
		c++;
	  }

	if (c > 1)
	  d = 1;
	if (c >= 1)
	  {
	    for (int i=0; i<4; i++)
	      {
		int cx = x + dir[i][0];
		int cy = y + dir[i][1];
		if (0 <= cx && cx < maze.size() && 0 <= cy && cy < maze[0].size())
		  if (!visited[cx][cy] && (maze[cx][cy] == '.' || maze[cx][cy] == '*'))
		    {
		      vector <int> tmp;
		      tmp.push_back(cx);
		      tmp.push_back(cy);
		      tmp.push_back(here[2] + d);
		      q.push(tmp);
		    }
	      }
	  }
      }

    return ret;
  }
   

};

Hard - WickedTeacher

本番中はopenしなかった。あとで見てみるも、解けなかった。ある整数A(非常に大きな値)が別の整数Kの倍数かどうかを判定する方法がわからなかった。editorial待ち。