TopCoder SRM 423 DIV 2

Problem	Check	Points
250	○	240.71
600	×	-
1000	-	-

一応1000まで手を出したんですが、600間違っててこれはひどい。
1000は実装問題という感じで、めんどいです。

TopCoder Statistics: SRM 423 Problem Set & Analysis

Problem 250 TheSimpleGame

問題

You have a n x n board and several checkers placed on it. The i-th checker is in the cell at row x[i], column y[i]. All coordinates are 1-based. There can be more than one checker in the same cell. A move consists of taking one checker and moving it one cell up, down, left or right.

You want to put each checker in one of the four corners of the board. Return the minimum number of moves necessary to achieve the goal.

My code

class TheSimpleGame {
public:
  int count(int n, vector <int> x, vector <int> y) {

	  int ans = 0;
	  for(int i=0 ; i<x.size() ; i++){
		  int xx = x[i];
		  int yy = y[i];

		  int mov = min(xx-1, n-xx) + min(yy-1, n-yy);
		  ans += mov;
	  }

	  return ans;
  }
};

Problem 600 TheTower

問題

N checkers are placed on an infinitely large board. The i-th checker is in the cell at row x[i], column y[i]. There can be more than one checker in the same cell. A move consists of taking one checker and moving it one cell up, down, left or right.

Return a int[] containing exactly N elements, where the i-th element (0-based) is the minimum number of moves necessary to end up with at least i+1 checkers in the same cell.

My code

// (x1,y1)と(x2,y2)の距離
int calcDist(int x1, int y1, int x2, int y2){
	return abs(x2-x1)+abs(y2-y1);
}

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

	  int size = x.size();
	  vector<int> ans;

	  for(int i=1 ; i<=size ; i++){
		  vector<int> v;

		  for(int m=0 ; m<size ; m++){
			  for(int n=0 ; n<size ; n++){
				  int xx = x[m];
				  int yy = y[n];

				  vector<int> dists;

				  for(int p=0 ; p<size ; p++){
					  dists.push_back(calcDist(xx, yy, x[p], y[p]));
				  }

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

				  int sum=0;
				  for(int p=0 ; p<i ; p++){
					  sum += dists[p];
				  }
				  v.push_back(sum);
			  }
		  }

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

		  ans.push_back(v[0]);
	  }

	  return ans;
  }
};

Problem 1000 TheEasyChase

問題

Two players play a simple game on a n x n board. The first player has a single white checker which is initially located at (rowWhite, colWhite). The second player has a single black checker which is initially located at (rowBlack, colBlack). All coordinates are 1-based. The two players alternate turns, and the first player moves first.

When it is the first player's turn, he chooses one of four directions (up, down, left or right) and moves his checker one cell in the chosen direction. When it is the second player's turn, he also chooses one of those four directions and moves his checker one or two cells in the chosen direction. A player wins the game when his move puts his checker in the cell occupied by his opponent's checker.

Both players use an optimal game strategy. If the player can win, he will follow the strategy that minimizes the number of moves in the game. If the player cannot win, he will follow the strategy that maximizes the number of moves in the game.

If the first player will win, return "WHITE x", and if the second player will win, return "BLACK x", where x is the number of moves in the game (all quotes for clarity).