TopCoder SRM 408 DIV 2

Problem	Check	Points
250	○	241.79
500	×	-
1000	-	-

500 -> 凡ミスというか、間違いだらけでがっくり。
1000 -> メモリサイズが壁に。最終的に1次元DPで書けたので良かった。

Problem 250 TournamentJudging

問題

You have just been hired to be a judge in the Thought Challenge Olympics. Your task is to calculate an overall score for a competitor based on his performance in a series of events. For each event, you have given him a raw score. The overall score is the sum of the adjusted scores for each event.

To calculate the adjusted score for an event, divide the raw score by the conversion factor for that event, and round the result to the nearest integer (.5 rounds up). You are given int[]s rawScores and conversionFactors. Element i of rawScores is the raw score you have given for the i-th event, and element i of conversionFactors is the conversion factor for the i-th event. Return the competitor's overall score.

My code

class TournamentJudging {
public:
  int getPoints(vector <int> rawScores, vector <int> conversionFactor) {
    int result = 0;

	for(int i=0 ; i<rawScores.size() ; i++){
		double tmp = (double)rawScores[i]/(double)conversionFactor[i];
		if(tmp-floor(tmp)>=0.5) result += (int)ceil(tmp);
		else result += (int)floor(tmp);
	}

    return result;
  }
};

Problem 500 OlympicCandles

To celebrate the upcoming Thought Challenge Olympics, you are going to follow tradition and light candles. On the first night of the event, you will light one candle. At the end of the night, you will extinguish the candle. On each subsequent night, you will light one more candle than you did on the previous night, so that on the n-th night (indexed from 1) you will light n candles (and extinguish them all in the morning). Each night that you light a candle, its height will decrease by 1 inch; once its height reaches 0 inches, you cannot use it anymore.

You are given a int[] candles, the i-th element of which is the height of the i-th candle that you own. Return the maximum number of nights you can celebrate the event without going to the store to get more candles. For example, if you have three candles of height 2, you can light one the first night, the other two on the second night, and then all three candles on the third night.

My code

class OlympicCandles {
public:
  int numberOfNights(vector <int> candles) {
	  bool end = false;
	  int i;

	  for(i=0 ; i<candles.size() ; i++){
		  sort(candles.begin(), candles.end(), greater<int>());

		  if(candles[0]==0) break;

		  for(int j=0 ; j<=i ; j++) 
			  candles[j]--;
		  
		  for(int j=0 ; j<candles.size() ; j++) 
			  if(candles[j]<0) end = true;
			  
		  if(end) break;
	  }
	  return i;
  }
};

Problem 1000 MarblesInABag

問題

Your friend Psycho Sid has challenged you to a game. He has a bag containing redCount red marbles and blueCount blue marbles. There will be an odd number of marbles in the bag, and you go first. On your turn, you reach into the bag and remove a random marble from the bag; each marble may be selected with equal probability. After your turn is over, Sid will reach into the bag and remove a blue marble; if there is no blue marble for Sid to remove, then he wins. If the final marble removed from the bag is blue, you will win. Otherwise, Sid wins.

Given the number of red and blue marbles in the bag, determine the probability that you win the game.

My code

const int MAX_N = 4001;

class MarblesInABag {
public:
  double getProbability(int redCount, int blueCount) {

	  double dp[MAX_N];
	  for(int i=0 ; i<=redCount ; i++) dp[i] = 0;

	  dp[redCount] = 1;
		
	  double ans = 0;
	  for(int j=blueCount ; j>=1 ; j--){
		  for(int i=redCount ; i>=0 ; i--){
			  if(i==0){
				  ans += dp[0];
				  dp[0] = 0;
				  continue;
			  }
			  if(i%2==j%2) continue;

			  //reach red;
			  dp[i-1] += dp[i]* (double)i/(double)(i+j);

			  // reach blue;
			  dp[i]   = dp[i]* (double)j/(double)(i+j);
		  }
	  }

	  return ans;
  }
};