TopCoder SRM 401 DIV 2

Problem	Check	Points
250	○	182.96
500	-	-
1000	-	-

250

時間はかかったけど、みんな軒並みSystem Testで死んでいくなか通れたのでOK。実はgcdでもっと簡単に書けたことを後に知る。
正答率は250にして32%。

500

いまだに「DPで出来るかな」という発想が抜け落ちているのが問題。時間内に提出できず。

1000

見てすらいない。

TopCoder Statistics

Problem 250 DreamingAboutCarrots

John works at a company called "FIELD-Tech", and today, he was so tired after work that he fell asleep as soon as he got home. Unfortunately, even in his sleep, he was unable to forget about his work. In one dream, he was asked to help a carrot producing company deal with the following question: how many carrots grow on a line segment connecting two given carrots? The endpoints of the segment (i.e., the two given carrots) should not be included. It's a rather strange question, and to make it even stranger, the company's representatives (guys who have carrots instead of heads) said that all the carrots grow on an infinite plane, and there is exactly one carrot at each point with integer coordinates. You must help tired John deal with this problem.

The coordinates of the two carrots are (x1, y1) and (x2, y2). Return the number of carrots that lie strictly on the line segment connecting these carrots.

class DreamingAboutCarrots {
public:
  int carrotsBetweenCarrots(int x1, int y1, int x2, int y2) {

	  int xx = abs(x2-x1);
	  int yy = abs(y2-y1);

	  if(xx==0 && yy==0) return 0; 

	  int cnt=1;

	  for(int i=2 ; i<=50 ; i++){
		  if(xx%i==0 && yy%i==0){
			  cnt *= i;
			  xx /= i;
			  yy /= i;
			  //cout << xx << " " << yy << endl;
			  i=1;
		  }
	  }
	  return cnt-1;
  }
};

Problem 500 FIELDDiagrams

A Ferrers diagram of the partition of positive number n = a1 + a2 + ... + ak, for a list a1, a2, ..., ak of k positive integers with a1 ≥ a2 ≥ ... ≥ ak is an arrangement of n boxes in k rows, such that the boxes are left-justified, the first row is of length a1, the second row is of length a2, and so on, with the kth row of length ak. Let's call a FIELD diagram of order fieldOrder a Ferrers diagram with a1 ≤ fieldOrder, a2 ≤ fieldOrder - 1, ..., ak ≤ fieldOrder - k + 1, so a FIELD diagram can have a number of rows which is less than or equal to fieldOrder. Your method will be given fieldOrder, it should return the total number of FIELD diagrams of order fieldOrder.

class FIELDDiagrams {
public:
  long long countDiagrams(int fieldOrder) {

	  ll dp[31][31];

	  for(int i=0 ; i<31 ; i++){
		  dp[0][i] = 0;
		  dp[i][0] = 0;
	  }

	  for(int i=1 ; i<31 ; i++){
		  for(int j=i ; j<31 ; j++){
			  dp[i][j] = dp[i-1][j]+dp[i][j-1]+1;
		  }

		  for(int j=i+1 ; j<31 ; j++){
			  dp[j][i] = dp[i][i];
		  }
	  }
	  return dp[fieldOrder][fieldOrder];
  }
};

Problem 1000 RunningLetters

There is an electronic sign above the entrance to FIELD-Tech headquarters. The sign displays a scrolling message that is repeated over and over again. The letters show up on one side of the sign, scroll to the other side, and then disappear. Polly, who works in the office, is curious about the length of the message. She has observed the sign for some period of time and written down the letters she has seen, in order. Now, you must help her determine the minimal possible length of the message. For example, if she saw the letters "abcabcabcab", two possible messages would be "bca" and "abcabc". The shortest possible length would be 3.

You will be given a String[] running. Concatenate the elements of running to get a space separated list of sections, each formatted "N S" (quotes for clarity), representing the concatenation of N instances of S. Expand out all the sections to get the entire text. For example, "3 abc 1 ab" expands out to "abcabcabcab" (3 instances of "abc" followed by 1 instance of "ab"). Return the minimal possible message length that could have produced the given text.