TopCoder SRM 404 DIV 2

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

（・3・）あっるぇー。どっちも1行追加したらSystem Test通過してへこんだ。

250
if(readParts.size()<3) return 0;

の行がなかったせいでsegmentation faultを吐くケースがあったんだけど、for文って最初に終了条件みないんだっけ？
と思ったら、readParts.size()の型がunsignedであることが悪さをしていたみたい。

for(int i=0 ; i<(signed)readParts.size()-2 ; i++)

でうまくいきました。

500
for(int ii=0 ; ii<v.size()*v.size() ; ii++)

と書くところを

for(int ii=0 ; ii<v.size() ; ii++)

と書いてました。どう見ても足りません、ただの凡ミスです。

1000

やる気がない。





TopCoder Statistics

Problem 250 ReadingBooks

There are some books, each consisting of exactly three parts: introduction, story and edification. There is a reader who goes through the books and reads various parts. Each time he finishes reading a part, he adds the name of the part to the end of a list. He may read zero or more parts from each book, and he can read them in any order, but he cannot read each part more than once. Whenever he starts reading a new book, he can no longer go back and read any parts of books he has looked at previously.

You are given a String[] readParts containing the list created by the reader. Each element of readParts is "introduction", "story" or "edification" (quotes for clarity). Return the maximum possible number of books for which the reader has read all three parts.

class ReadingBooks {
public:
  int countBooks(vector <string> readParts) {
	  if(readParts.size()<3) return 0;

	  vector<string> v;
	  v.push_back("introduction");
	  v.push_back("edification");
	  v.push_back("story");

	  sort(v.begin(), v.end());

	  int cnt=0;
	  for(int i=0 ; i<readParts.size()-2 ; i++){
		  vector<string> vv;
		  vv.clear();

		  vv.push_back(readParts[i]);
		  vv.push_back(readParts[i+1]);
		  vv.push_back(readParts[i+2]);

		  sort(vv.begin(), vv.end());

		  if(v==vv){
			  cnt++;
			  i+=2;
		  }
	  }

	  return cnt;
  }
};

Problem 500 RevealTriangle

Suppose there is a triangle of digits like the following:

74932
1325
457
92
1
Each digit, with the exception of those in the top row, is equal to the last digit of the sum of its upper and upper-right neighboring digits.

You will be given a String questionMarkTriangle containing a triangle where only one digit in each row is known and all others are represented by '?'s (see example 0 for clarification). Each element of questionMarkTriangle represents a row of the triangle, and the rows are given from top to bottom. Each element contains exactly one digit ('0'-'9') and the remaining characters are all '?'s. Restore the triangle and return it as a String without '?'s.

int calc(int a, int b, int c, int type){
	int tmp;
	if(type==0){
		tmp = c-b;
		if(tmp<0) return tmp+10;
		return tmp;
	}

	else if(type==1){
		tmp = c-a;
		if(tmp<0) return tmp+10;
		return tmp;
	}

	else{
		tmp = a+b;
		return tmp%10;
	}
}

class RevealTriangle {
public:
  vector <string> calcTriangle(vector <string> questionMarkTriangle) {

	  vector<string> v = questionMarkTriangle;

	  for(int ii=0 ; ii<v.size()*v.size() ; ii++){
	  for(int i=0 ; i<v.size() ; i++){
		  for(int j=0 ; j<v.size()-i-1 ; j++){
			  char c[3];
			  c[0] = v[i][j];
			  c[1] = v[i][j+1];
			  c[2] = v[i+1][j];


			  int cnt=0;
			  for(int k=0 ; k<3 ; k++){
				  if(c[k]=='?') cnt++;
			  }


			  if(cnt>=2 || cnt==0) continue;

			  if     (c[0]=='?') v[i][j] = calc(c[0], c[1], c[2], 0)+48;
			  else if(c[1]=='?') v[i][j+1] = calc(c[0], c[1], c[2], 1)+48;
			  else if(c[2]=='?') v[i+1][j] = calc(c[0], c[1], c[2], 2)+48;
		  }
	  }
	  }
	  return v;
  }
};

Problem 1000 GetToTheTop

Little John has found a set of stairs where each stair might contain a number of sweets. He wants to collect as many of these sweets as possible. Each stair can be described as a line segment in the Cartesian plane parallel to the x-axis and having a positive y-coordinate. These segments don't overlap and don't have common endpoints. When John is on a stair, he can move freely between its two endpoints and can collect all sweets on it. He can jump from a point on one stair to a point on another stair (including endpoints of stairs) if the Euclidean distance between them is less than or equal to K. He can only jump to stairs where the y-coordinate is greater than or equal to his current y-coordinate.

You are given a int sweets, the i-th element of which is the number of sweets on the i-th stair. You are also given ints x, y and stairLength. The coordinates of the leftmost point of the i-th stair are (x[i], y[i]) and the horizontal length of that stair is stairLength[i]. John starts at point (0, 0) and can move wherever he wants along the x-axis before making his first jump. He can first jump to any point on any stair (including endpoints of stairs) as long as the Euclidean distance between the initial and the final points of the jump does not exceed K. Return the maximum possible number of sweets he can collect.