TopCoder SRM 422 DIV 2

Problem	Check	Points
250	◯	231.00
500	◯	229.16
1000	-	-

久しぶりに500正解！初めてDP使って問題に答えられたので嬉しい。1000は力尽きてやる気力がなくて、残り25分ぐらいあったけどアイス食ってました。

TopCoder Statistics: SRM 422 Problem Set & Analysis

Problem 250 MultiNumber

問題

A number is a multi number if its decimal representation can be split into two numbers, such that the product of all the digits in the first number is equal to the product of all the digits in the second number. For example, 1221 is a multi number because it can be split into 12 and 21, and 1 * 2 = 2 * 1. 1236 is also a multi number, but 1234 is not. Note that you can only split a number into two sequences of consecutive digits, where each sequence contains at least one digit. So, for example, we can only split 12345 in four different ways: 1-2345, 12-345, 123-45, 1234-5. You will be given an int number. Return "YES" if it is a multi number, or "NO" otherwise (all quotes for clarity).

My code

deque<int> integerDigits(int x){
	deque<int> arr;
	while(x!=0){
		arr.push_front(x%10);
		x/=10;
	}
	return arr;
}


class MultiNumber {
public:
  string check(int number) {

	  deque<int> n = integerDigits(number);

	  for(int i=1 ; i<n.size() ; i++){

		  int a = 1;
		  for(int j=0 ; j<i ; j++){
			  a *= n[j];
		  }

		  int b = 1;
		  for(int j=i ; j<n.size() ; j++){
			  b *= n[j];
		  }

		  if(a==b) return "YES";
	  }

	  return "NO";
  }
};

Problem 500 PrimeSoccer

問題

You are watching a soccer match, and you wonder what the probability is that at least one of the two teams will score a prime number of goals. The game lasts 90 minutes, and to simplify the analysis, we will split the match into five-minute intervals. The first interval is the first five minutes, the second interval is the next five minutes, and so on. During each interval, there is a skillOfTeamA percent probability that team A will score a goal, and a skillOfTeamB percent probability that teamB will score a goal. Assume that each team will score at most one goal within each interval. Return the probability that at least one team will have a prime number as its final score.

My code

double dp[20][20];

vector<double> calcdp(int skill){
	for(int i=0 ; i<20 ; i++){
		for(int j=0 ; j<20 ; j++){
			dp[i][j] = 0;
		}
	}

	// Points+1 - Round
	dp[1][0] = 1;

	for(int j=1; j<20 ; j++){
		for(int i=1 ; i<20 ; i++){
			dp[i][j] = dp[i-1][j-1]*(double)skill/100 + dp[i][j-1]*(double)(100-skill)/100;
		}
	}


	vector<double> ans;

	for(int i=1 ; i<20 ; i++){
		ans.push_back(dp[i][18]);
	}

	return ans;
}

bool isPrime(int num){
	if(num <2) return false;
	for(int i=2 ; i<num ; i++){
		if(num%i==0) return false;
	}
	return true;
}


class PrimeSoccer {
public:
  double getProbability(int skillOfTeamA, int skillOfTeamB) {
    double result = 0;

	vector<double> teamA = calcdp(skillOfTeamA);
	vector<double> teamB = calcdp(skillOfTeamB);

	
	for(int i=0 ; i<teamA.size() ; i++){
		cout << teamA[i] << " " << teamB[i] << endl;
	}
	

	for(int i=0 ; i<teamA.size(); i++){
		for(int j=0 ; j<teamB.size() ; j++){
			if(isPrime(i) || isPrime(j)){
				result += teamA[i]*teamB[j];
			}
		}
	}

    return result;
  }
};

Problem 1000 BirthdayCake

問題

You are going to make a fruit birthday cake for a party. There are several kinds of fruit you can choose from, and you must choose at least K different kinds to put on the cake. However, some of your friends don't like certain kinds of fruits, and they will refuse to eat a cake containing any of those fruits. You want as many of your friends as possible to eat the cake.

You are given a String availableFruits, where each element is a kind of fruit that you can put on the cake. You are also given a String friendsDislikings, where each element is a space-separated list of the kinds of fruits that one of your friends doesn't like. Return the largest number of friends that can eat the cake, assuming that you must use at least K different kinds of fruits.