TopCoder SRM 407 DIV 2

Problem	Check	Points
250	○	145.71
500	○	324.04
1000	-	-

今回はどれもプログラムが長くなっちゃった

TopCoder Statistics: SRM 407 Problem Set & Analysis

Problem 250 SpiralWalking

問題

You are playing a game where you must traverse a rectangular grid of cells using a spiral path. The map is given in a String[] levelMap, where the j-th character of the i-th element is the number of points associated with the cell in row i, column j. Rows are numbered from top to bottom, starting at 0, and columns are numbered from left to right, starting at 0. All coordinates in this problem will be given as (row, column).

You start at cell (0,0), the top left corner of the grid. You are facing right. You move by repeating the following strategy until you have visited every single cell on the grid exactly once. If there is an adjacent cell in front of you that you haven't visited yet, move forward to that cell. Otherwise, if there are still unvisited cells on the grid, turn 90 degrees clockwise.

To calculate your final score, add up all the points for the cells that you visited, but don't include the cells in which you changed direction. The first and last cells in your path will always be included in your final score.

See examples for further clarification.

My code

bool inRange(int x, int y){ return 0<=x && x < y;}

class SpiralWalking {
public:
  int totalPoints(vector <string> levelMap) {
    int result = 0;

	enum dir{
		LEFT,
		RIGHT,
		UP,
		DOWN
	};

	enum dir d = RIGHT;

	bool m[51][51];

	int height = levelMap.size();
	int width = levelMap[0].size();

	for(int i=0 ; i<height ; i++){
		for(int j=0 ; j<width ; j++){
			m[i][j] = false;
		}
	}

	result += levelMap[0][0]-48;
	m[0][0] = true;

	int ni=0, nj=0;

	while(1){
		if(d==RIGHT){
			if(inRange(nj+1, width) && !m[ni][nj+1]){
				nj++;
				result += levelMap[ni][nj]-48;
				m[ni][nj] = true;
			}
			else{
				result -= levelMap[ni][nj]-48;
				d = DOWN;
			}
		}
		else if(d==DOWN){
			if(inRange(ni+1, height) && !m[ni+1][nj]){
				ni++;
				result += levelMap[ni][nj]-48;
				m[ni][nj] = true;
			}
			else{
				result -= levelMap[ni][nj]-48;
				d = LEFT;
			}
		}
		else if(d==LEFT){
			if(inRange(nj-1, width) && !m[ni][nj-1]){
				nj--;
				result += levelMap[ni][nj]-48;
				m[ni][nj] = true;
			}
			else{
				result -= levelMap[ni][nj]-48;
				d = UP;
			}
		}
		else if(d==UP){
			if(inRange(ni-1, height) && !m[ni-1][nj]){
				ni--;
				result += levelMap[ni][nj]-48;
				m[ni][nj] = true;
			}
			else{
				result -= levelMap[ni][nj]-48;
				d = RIGHT;
			}
		}
		//cout << ni << " " << nj << " " << result << endl;

		if( 
		(!inRange(ni+1, height) || m[ni+1][nj])&&
		(!inRange(ni-1, height) || m[ni-1][nj])&&
		(!inRange(nj+1 ,width) || m[ni][nj+1])&&
		(!inRange(nj-1 ,width) || m[ni][nj-1])) break;

	}

	
    return result;
  }
};

Problem 500 CorporationSalary

問題

You are working in the HR department of a huge corporation. Each employee may have several direct managers and/or several direct subordinates. Of course, his subordinates may also have their own subordinates, and his direct managers may have their own managers. We say employee X is a boss of employee Y if there exists a sequence of employees A, B, ..., D, such that X is the manager of A, A is the manager of B, and so on, and D is the manager of Y (of course, if X is a direct manager of employee Y, X will be a boss of employee Y). If A is a boss of B, then B can not be a boss of A. According to the new company policy, the salary of an employee with no subordinates is 1. If an employee has any subordinates, then his salary is equal to the sum of the salaries of his direct subordinates.

You will be given a String[] relations, where the j-th character of the i-th element is 'Y' if employee i is a direct manager of employee j, and 'N' otherwise. Return the sum of the salaries of all the employees.

My code

ll s[51];

class CorporationSalary {
public:
  long long totalSalary(vector <string> relations) {
	  int n = relations.size();

	  // for local
	  for(int i=0 ; i<n ; i++){
		  s[i] = 0;
	  }

	  bool end;
	  bool noY;

	  for(int k=0 ; k<n ; k++){

		  for(int i=0 ; i<n ; i++){
			  end = false;
			  noY = true;
			  ll tmp = 0;

			  for(int j=0 ; j<n ; j++){
				  if(relations[i][j]=='Y'){
					  if(s[j]==0){
						  end = true;
						  break;
					  }
					  tmp += s[j];
					  noY = false;
				  }  

			  }
			  if(end) continue;

			  if(noY) s[i]=1;
			  else s[i] = tmp;
		  }

		  /*
		  for(int i=0 ; i<n ; i++){
			  cout << s[i] << " ";
		  }
		  cout << endl;
		  */
	  }

	  ll ans = 0;
	  for(int i=0 ; i<n ; i++) ans += s[i];
	  
	  return ans;
  }
};

Problem 1000 CheapestRoute

問題

There is a long corridor which consists of a single horizontal row of n cells, numbered 0 to n-1 from left to right. You are standing in the leftmost cell and you want to move to the rightmost cell. From each cell, you can walk left or right to an adjacent cell. It costs cellPrice[i] to walk into cell i. If the price of a cell is -1, you cannot walk into it.

Some cells may also contain teleports. The i-th teleport is located in cell enterCell[i], and when you use that teleport, it will take you to cell exitCell[i]. It costs teleportPrice+x to use a teleport, where x is the number of teleports you have used previously. When you enter a cell i using a teleport, you do not have to pay cellPrice[i] - you only pay the teleport price. However, if the price of a cell is -1, you cannot enter that cell using a teleport.

Determine the minimal total cost C required to reach the rightmost cell. Then, determine the minimum number of moves M required to reach the rightmost cell using that minimal cost C. Walking to an adjacent cell counts as a single move, and using a teleport counts as a single move. Return a int containing exactly two elements. The first element should be C and the second element should be M. If it is impossible to reach the rightmost cell, return an empty int instead.

My code

const int INF = 99999999;

int mincost;
int minstep;

vector<int> ccellPrice;
vector<int> eenterCell;
vector<int> eexitCell;
int tteleportPrice;

struct s{
	int scost;
	int sstep;
	int steleport;
	bool used;
};

s cell[51];

void dfs(int pos, int cost, int step, int tcnt){
	
	if(cell[pos].scost==INF){
		cell[pos].scost = cost;
		cell[pos].sstep = step;
		cell[pos].steleport = tcnt;
	}

	else if(cell[pos].scost > cost &&
		cell[pos].sstep > step &&
		cell[pos].steleport > tcnt){
		
		cell[pos].scost = cost;
		cell[pos].sstep = step;
		cell[pos].steleport = tcnt;
	}
	
	else if(cell[pos].scost <= cost &&
		cell[pos].sstep <= step &&
		cell[pos].steleport <= tcnt){
			return;
	}
	

	if(mincost < cost || step > ccellPrice.size()) return;

	if(pos == ccellPrice.size()-1){
		if(mincost == cost && minstep < step) return;
		mincost = cost;
		minstep = step;
		return;
	}

	if(ccellPrice[pos+1]!=-1 && !cell[pos+1].used){
		cell[pos+1].used = true;
		dfs(pos+1, cost + ccellPrice[pos+1], step+1, tcnt);
		cell[pos+1].used = false;
	}

	if(cost + tteleportPrice <= mincost){
		for(int i=0 ; i<eenterCell.size() ; i++){
			if(eenterCell[i]==pos && ccellPrice[eexitCell[i]]!=-1 && cell[eexitCell[i]].used==false){
				cell[eexitCell[i]].used = true;
				dfs(eexitCell[i], cost + tteleportPrice + tcnt, step+1, tcnt+1);
				cell[eexitCell[i]].used = false;
			}
		}
	}

	if(pos!=0 && ccellPrice[pos-1]!=-1 && !cell[pos-1].used){
		cell[pos-1].used = true;
		dfs(pos-1, cost + ccellPrice[pos-1], step+1, tcnt);
		cell[pos-1].used = false;
	}

	return;
}


class CheapestRoute {
public:
  vector <int> routePrice(vector <int> cellPrice, vector <int> enterCell, vector <int> exitCell, int teleportPrice) {

	  if(cellPrice.back()==-1) return vector<int>();

	  for(int i=0 ; i<cellPrice.size() ; i++){
		  cell[i].used = false;
		  cell[i].scost = INF;
		  cell[i].sstep = INF;
		  cell[i].steleport = INF;
	  }

	  mincost = INF;
	  minstep = INF;
	  ccellPrice = cellPrice;
	  eenterCell = enterCell;
	  eexitCell = exitCell;
	  tteleportPrice = teleportPrice;

	  dfs(0, 0, 0, 0);

	  vector<int> ans;
	  if(minstep == INF){
		  return ans;
	  }
	  ans.push_back(mincost);
	  ans.push_back(minstep);
	  return ans;
  }
};