TopCoder SRM 417 DIV 2

Problem	Check	Points
250	○	242.85
500	○	209.76
1000	-	-

250はあらかじめIntegerDigitsとFromDigitsをほぼそのまま使い回し。ちょっとずるい？
500はちょっと手間取ったけど大きなバグもなくさらっといけた。最近のものよりレベルが低い気がする・・・

TopCoder Statistics: SRM 417 Problem Set & Analysis

Problem 250 ReversedSum

問題

For a given positive integer X we can obtain the reversed positive integer Rev(X) by reversing the order of X's digits and removing leading zeroes. For example, if X = 123 then Rev(X) = 321; and if X = 100, then Rev(X) = 1.

You will be given two positive integers x and y. Return their reversed sum, which is defined as Rev(Rev(x) + Rev(y)).

My code

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

int fromDigits(deque<int> arr){
	int x=0;
	while(!arr.empty()){
		x *= 10;
		x += arr[0];
		arr.pop_front();
	}
	return x;
}

class ReversedSum {
public:
  int getReversedSum(int x, int y) {

	int a =  fromDigits(revIntegerDigits(x)) + fromDigits(revIntegerDigits(y));
	return fromDigits(revIntegerDigits(a));
  }
};

Problem 500 TemplateMatching

問題

In this problem you will be given a String text and you will need to find the substring of the text that matches a given template in the best way. The template will be represented by two Strings: prefix and suffix. Consider a string S. The prefix match score of S with respect to a given template is the maximal n >= 0 such that the first n characters of S are equal to the last n characters of prefix and occur in the same exact order. Analogously, the suffix match score of S is the maximal m >= 0 such that the last m characters of S are equal to the first m characters of suffix and occur in the same exact order.

For example, if S = "something", prefix = "awesome", and suffix = "ingenious", than the prefix score of S is 4 (the matched characters are "some") and the suffix score is 3 (the matched characters are "ing").

The match score of a string S with respect to a given template is the sum of its prefix and suffix match scores. Find the non-empty substring of text with the maximal match score according to the template (prefix, suffix). In case of a tie, return the substring with the maximal prefix score. If there are still several candidates, return one that comes first lexicographically.

My code

string ttext, pprefix, ssuffix;
int maxscore, maxpscore;
vector<string> vstr;

void calcScore(string str){

	// prefix
	int pscore = 0;
	int ptmpmin = min(pprefix.size(), str.size());

	for(int i=ptmpmin ; i>=0 ; i--){
		string a = pprefix.substr(pprefix.size()-i);
		string b = str.substr(0,i);

		if(a==b){
			pscore = i+1;
			break;
		}
	}

	// suffix
	int sscore = 0;
	int stmpmin = min(ssuffix.size(), str.size());
	
	for(int i=stmpmin ; i>=0 ; i--){
		string a = str.substr(str.size()-i);
		string b = ssuffix.substr(0,i);

		if(a==b){
			sscore = i+1;
			break;
		}
	}

	int score = pscore+sscore;

	if(maxscore > score || maxpscore > pscore) return;

	if(maxscore == score && maxpscore == pscore) vstr.push_back(str);

	else{
		maxscore = score;
		maxpscore = pscore;
		vstr.clear();
		vstr.push_back(str);
	}
}

class TemplateMatching {
public:
  string bestMatch(string text, string prefix, string suffix) {
	ttext = text;
	pprefix = prefix;
	ssuffix = suffix;

	maxscore = 0;
	maxpscore = 0;
	vstr.clear();

	int tsize = text.size();

	for(int i=0 ; i<tsize ; i++){
		for(int j=1 ; i+j<=tsize ; j++){
			calcScore(text.substr(i,j));
		}
	}

	sort(vstr.begin(), vstr.end());
	return vstr[0];
  }
};

Problem 1000 TripleJump

問題

The triple jump works as follows. The athlete runs down a runway until he reaches a designated mark. He then makes three consecutive jumps and lands in a sand-filled box. The length of the triple jump is the sum of the lengths of the three consecutive jumps. The winner of the competition is the athlete with the longest triple jump.

You are taking part in the competition and jumping after all your opponents. Since you are the last to jump, you already know all your opponents' results. They are given in the int opponents, where opponents[i] is the length of the i-th opponent's triple jump in centimeters.

You have already made the first of your three jumps, and it was first centimeters long. You ask yourself a question: "What is the probability that I will take first place? Second place? And all the other places?". You know that each of your two remaining jumps will be between lower and upper centimeters, inclusive, in length. The lengths will not necessarily be integers, and all possible lengths between lower and upper will be equally likely. Return a double containing exactly N + 1 elements (N is the number of opponents you have) such that the i-th element (0-indexed) is the probability of you taking (i+1)-th place. Note that your place number is equal to one plus the number of opponents who had longer triple jumps than you.