TopCoder SRM 402 DIV 2

C++ TopCoder
Problem Check Points
250 ○ 237.18
500 × -
1000 - -

250は軽いジャブ。500はConstraintsがすごく少なくて、例外をきちんとチェックしきれていなかった。再提出までしたのに・・・
1000は・・・確率が苦手。期待値をしっかり理解しないと。
そういえば今日は練習会中に真っ赤な人が降臨してどっきどきでした。

TopCoder Statistics

Problem 250 WordAbbreviation

You are given a String words, each element of which is a single word. Return a String where the i-th element is the abbrevation for the i-th word. The abbreviation for a word is its shortest non-empty prefix that is not a prefix of any other given word. The constraints will guarantee that it is possible to find an abbreviation for all the given words.

class WordAbbreviation {
public:
  vector <string> getAbbreviations(vector <string> words) {
	  vector<string> ans;
	  ans.clear();

	  for(int i=0 ; i<words.size() ; i++){
		  for(int j=1 ; j<=words[i].size() ; j++){
			  string s = words[i].substr(0,j);

			  bool f = true;
			  for(int k=0 ; k<words.size() ; k++){
				  if(k==i) continue;
				  if(s == words[k].substr(0,j)) f = false;
			  }
			  if(f){
				  ans.push_back(s);
				  break;
			  }
		  }
	  }
	  return ans;
  }
};

Problem 500 ConsecutiveNumbers

Your little son has written some consecutive positive integers on a piece of paper, in no particular order. Each integer was written exactly once. He then erased one of the integers and showed you the remaining ones. Do you know which number your son erased?

Formally, a list of positive integers is said to be consecutive if there are two positive integers a and b such that every integer between a and b, inclusive, appears in the list exactly once.

For example, if the remaining numbers are (10,7,12,8,11), the only possible missing number is 9. If the remaining numbers are (2,3), the missing number could be either 1 or 4. If the remaining numbers are (3,6), your son must have made a mistake.

You are given the remaining numbers in a int numbers. Return a int containing all the possible numbers your son might have erased. The numbers should be sorted in ascending order, and there should be no duplicates. If your son made a mistake, return an empty int[].

bool isConsecutive(vector<int> v){
	int minnum = v.front();
	for(int i=0 ; i<v.size() ; i++){
		if(minnum+i != v[i]) return false;
	}
	return true;
}

bool includeSame(vector<int> v){
	for(int i=0 ; i<v.size()-1 ; i++){
		if(v[i]==v[i+1]) return true;
	}
	return false;
}

class ConsecutiveNumbers {
public:
  vector <int> missingNumber(vector <int> numbers) {
	  
	  sort(numbers.begin(), numbers.end());

	  int minnum = numbers[0];
	  int maxnum = numbers.back();

	  //cout << minnum << " " << maxnum << endl;
	  if(includeSame(numbers)) return vector<int>();


	  if( numbers.size()-1 == maxnum-minnum && isConsecutive(numbers) ){
		  vector<int> v;
		  if(minnum-1>0) v.push_back(minnum-1);
		  v.push_back(maxnum+1);

		  return v;
	  }

	  else if(numbers.size() == maxnum-minnum && !isConsecutive(numbers) ){
		  for(int i=0 ; i<numbers.size() ; i++){
			  if(numbers[i] != i+minnum){
				  vector<int> v;
				  v.push_back(i+minnum);
				  return v;
			  }
		  }
	  }
	  
	 return vector<int>();
  }
};

Problem 1000 RandomSort

You are given a int[] permutation containing a permutation of the first n positive integers (1 through n), and you want to sort them in ascending order. To do this, you will perform a series of swaps. For each swap, you consider all pairs (i, j) such that i < j and permutation[i] > permutation[j]. Among all those pairs, you choose one randomly and swap permutation[i] and permutation[j]. Each pair has the same probability of being chosen. Return the expected number of swaps needed to sort permutation in ascending order.

map<vector<int>, double> memo;

class RandomSort {
public:
  double getExpected(vector <int> permutation) {
	double sum=0;
	int cnt=0;

	if(memo.count(permutation)) return memo[permutation];

	for(int i=0 ; i<permutation.size() ; i++){
		for(int j=i+1 ; j<permutation.size() ; j++){
			if(permutation[i] > permutation[j]){
				// swap
				int tmp = permutation[j];
				permutation[j] = permutation[i];
				permutation[i] = tmp;

				sum += getExpected(permutation);
				cnt++;

				tmp = permutation[j];
				permutation[j] = permutation[i];
				permutation[i] = tmp;
			}
		}
	}
    
	// sum/cnt -> 1つ前の状態の期待値の合計を、状態数で割る
	// 1つ前の状態数なので、1を加えて現在の期待値にする
	if(cnt) sum = sum/cnt+1;
	return memo[permutation] = sum;

  }
};