TopCoder SRM 411 DIV 2

C/C++ TopCoder
Problem Check Points
250 × -
600 × -
900 - -

0点きた！はぁ・・・250は解けようよ。すっごい凡ミスでした。
600はDPを使って解く、ということなのですっげー時間をかけて理解しました。自分で書ける気がしない。

TopCoder Statistics: SRM 411 Problem Set & Analysis

Problem 250 MaximumScoredNumber

問題

In her favorite Math class, Little Bonnie learned that some non-negative integers can be represented as the sum of the squares of two non-negative integers. For example, 13 can be represented as 2*2 + 3*3.

Bonnie later discovered that some of those integers can even be represented by more than one possible pair. For example, 25 can be represented as 0*0 + 5*5, and it can also be represented as 3*3 + 4*4.

She has defined the score of an integer as the number of different ways it can be represented as the sum of the squares of two non-negative integers. The order of the two squared integers is not important. In other words, a*a + b*b is equivalent to b*b + a*a, so they should only count once in the score. So, 25 has a score of 2, 2 has a score of 1 (2 = 1*1 + 1*1), 1 also has a score of 1 (1 = 0*0 + 1*1) and 3 has a score of 0.

Bonnie needs your help in solving the following problem. She wants to find the integer between lowerBound and upperBound, inclusive, with the maximum score. If multiple integers have the same highest score, return the largest among them.

My code
int score(int a){
	int end = (int)sqrt((double)a);

	int cnt = 0;
	for(int i=0 ; i<= end ; i++){
		for(int j=i ; j<= end ; j++){
			if(i*i+j*j==a) cnt++;
		}
	}
	return cnt;
}

class MaximumScoredNumber {
public:
  int getNumber(int lowerBound, int upperBound) {
	  int result=100000;
	  int maxscore = 0;
	  int maxi = -1;

	  for(int i=upperBound; i>=lowerBound ; i--){
		  if(score(i) > maxscore){
			  maxscore = score(i);
			  maxi = i;
		  }
	  }

	  if(maxi==-1) return lowerBound;
	  return maxi;
  }
};

Problem 600 SentenceDecomposition

問題

Little Bonnie and her friends were dismayed to learn that their parents were reading all of their private communications. They decided to invent a new language that would allow them to talk freely. What they finally came up with was a language where sentences are built using a special method.

All the valid words that can be used in the new language are given in the String[] validWords. A sentence is a concatenation (with no spaces) of a sequence of valid words. Each valid word can appear 0 or more times in the sentence. What makes the language special is that each word can be transformed by rearranging its letters before being used. The cost to transform a word is defined as the number of character positions where the original word and the transformed word differ. For example, "abc" can be transformed to "abc" with a cost of 0, to "acb", "cba" or "bac" with a cost of 2, and to "bca" or "cab" with a cost of 3.

Although several different sequences of valid words can produce the same sentence in this language, only the sequence with the least total transformation cost carries the meaning of the sentence. The advantage of the new language is that the parents can no longer understand what the kids are saying. The disadvantage is that the kids themselves also do not understand. They need your help.

Given a String sentence, return the total cost of transformation of the sequence of valid words which carries the meaning of the sentence, or -1 if no such sequence exists.

My code
string ssentence;
vector< string > vvalidWords;

int cost(string a, string b){
	if(a.size()!=b.size()) return -1;

	string aa = a;
	string bb = b;

	sort(aa.begin(), aa.end());
	sort(bb.begin(), bb.end());
	if(aa!=bb) return -1;

	int cnt = 0;
	for(int i=0 ; i<a.size() ; i++) if(a[i]!=b[i]) cnt++;
	return cnt;
}

const int MAXCNT = 1000;
const int INF = 9999999;
int dp[MAXCNT];

int calc(){
	dp[0] = 0;

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

		int mincnt = INF;
		for(int j=0 ; j<i ; j++){
			if(dp[j]==-1) continue;

			string sub = ssentence.substr(j, i-j);
			cout << i << " " << j << " " <<  sub << endl;
			int tmpmin = INF;

			for(int k=0 ; k<vvalidWords.size() ; k++){
				int t = cost(vvalidWords[k], sub);

				if(t!=-1) tmpmin = min(tmpmin,t);
			}
			mincnt = min(mincnt, tmpmin+dp[j]);
		}

		if(mincnt == INF) dp[i] = -1;
		else              dp[i] = mincnt;

		for(int j=0 ; j<ssentence.size() ; j++){
			cout << dp[j] << " ";
		}
		cout << endl;
	}
	return dp[ssentence.size()];
}

class SentenceDecomposition {
public:
  int decompose(string sentence, vector <string> validWords) {
	  ssentence = sentence;
	  vvalidWords = validWords;

	  return calc();
  }
};

Problem 1000 HoleCakeCuts

問題

Little Bonnie has been given a special cake as a reward for her good performance in her Math class. When viewed from above, the cake is a square, with an empty square hole inside. Both squares are centered at (0, 0) and their sides are parallel to the x- and y-axes.

Bonnie is going to cut the cake using several horizontal and vertical cuts. These cuts are given in the int[]s horizontalCuts and verticalCuts. The i-th horizontal cut is a line parallel to the x-axis which goes through the point (0, horizontalCuts[i]). Likewise, the i-th vertical cut is a line parallel to the y-axis which goes through the point (verticalCuts[i], 0). All cuts have infinite lengths.

You are given an int cakeLength, half of the side length of the outer square, and an int holeLength, half of the side length of the inner square hole. Note that both of these numbers are halves of the sides of the corresponding squares. Return the number of pieces of cake that will exist after all the cuts are performed.