TopCoder SRM 409 DIV 2

Problem	Check	Points
250	○	163.53
500	×	-
1000	-	-

250 -> 時間かかりすぎ。
500 -> 文字列問題は苦手だ・・・コードが増えるわかめちゃん。

Problem 250 Stick

問題

Little Johnny has a stick that is 64 centimeters long, but he thinks it would be more fun to play with a stick that is x centimeters long. He decides to break the original stick into a number of smaller sticks, and then glue them together to get a stick that is exactly x centimeters long.

The easiest way to break a stick is to break it in half, so Johnny will use the following procedure:

1. Sum the lengths of all the sticks (initially, there is just one 64 centimeter stick). While this sum is greater than x, repeat the following:
   • Take one of the sticks with the shortest length and break it in half.
   • If discarding one of the halves would not make the sum of the remaining sticks' lengths less than x, throw that half away.
2. Finally, glue the remaining sticks together to form a stick that is x centimeters long.

Return the number of sticks Johnny would have to glue together in the final step if he follows the above procedure. If he has only one stick when he gets to the final step, return 1 (see example 0).

My code

int sum(vector<int> v){
	int n=0;
	for(int i=0;i<v.size() ; i++){
		n += v[i];
	}
	return n;
}

class Stick {
public:
  int pieces(int x) {
    int result=0;
	vector<int> v;
	v.push_back(64);

	while(1){
		if(x==sum(v)) break;
		int tmp = v.back();
		v.pop_back();
		v.push_back(tmp/2);
		if(sum(v)<x) v.push_back(tmp/2);
	}
    return v.size();
  }
};

あとで書きなおしたもの↓

int bitCount(int N){
	int bit = 1, count=0;
	for(int i=0 ; i<sizeof(int)*8 ; i++){
		if(N&bit) count++;
		bit <<=1;
	}
	return count;
}

class Stick {
public:
  int pieces(int x) {
	  return bitCount(x);
  }
};

Problem 500 OrderedSuperString

問題

A string X is an ordered superstring of the String[] words if

• Each element of words is a substring of X.
• There exists a sequence of indices x_1 <= x_2 <= ... <= x_n, where n is the number of elements in words. For each element k of words, where k is a 1-based index, there is an occurrence of words[k] that starts at the x_k-th letter of X.

For example "abca" is an ordered superstring of {"abc", "ca"}, but "cabc" is not.
Given a String[] words, return the length of its shortest ordered superstring.

My code

int pos;

string combine(string s1, string s2){
	string s;

	if(s1.size() >= s2.size()){
		for(int i=pos ; i<s1.size() ; i++){
			int n = min(s2.size(), s1.size()-i);

			string ss1 = s1.substr(i,n);
			string ss2 = s2.substr(0,n);

			//cout << ss1 << " " << ss2 << endl;

			if(ss1==ss2){
				if(n==s2.size()) s=s1;
				else s = s1+s2.substr(n);
				pos = i;
				break;
			}
		}
	}
	else{
		for(int i=pos ; i<s1.size() ; i++){
			
			string ss1 = s1.substr(i);
			string ss2 = s2.substr(0,s1.size()-i);

			if(ss1==ss2){
				s = s1 + s2.substr(s1.size()-i);
				pos = i;
				break;
			}
		}
	}
	
	if(s==""){
		pos = s1.size();
		return s1+s2;
	}

	return s;
}

class OrderedSuperString {
public:
  int getLength(vector <string> words) {
	  pos = 0;
	 
	  for(int i=0 ; i<words.size()-1 ; i++){
		  string s1 = words[i];
		  string s2 = words[i+1];

		  string sss = combine(s1,s2);
		  //cout << s1 << " " << s2 << " " << sss << pos << endl;

		  words[i+1] = sss;
	  }
	  return words[(signed)words.size()-1].size();
  }
};

Problem 1000 TeleportsNetwork

問題

The Kingdom of Byteland has a big capital city that is the center of its industry and social life. To connect every city to the capital, the King decided to develop a network of roads. Each city, except for the capital, was responsible for building a single bidirectional road from itself to another city. For each city X, the following algorithm was used to determine the destination of the road built by that city:

• Measure the Euclidean distances from all the cities to the capital, and consider only those which are strictly closer to the capital than city X (include the capital in that list).
• If there is more than 1 city, pick the city which is closest to city X.
• If there are multiple such cities, pick the city among them with the smallest X coordinate.
• If there are still multiple such cities, pick the city among them with the smallest Y coordinate.

After all the roads were built, some people started to complain that they had to go through too many other cities to get to the capital. The King decided to construct teleportCount teleports to solve this problem. Each teleport would provide an instant connection between the city where it is placed and the capital.

Let's define the inconvenience of a city as the minimal number of roads one needs to follow to get from that city to the capital, or to a city with a teleport. For example, the inconvenience of the capital, and of all cities with teleports, is 0. The inconvenience of a city that doesn't have a teleport but is directly connected to the capital or to a city with a teleport is 1, and so on. Note that the shortest route from a city to the capital may involve traveling further away from the capital to reach a teleport.

The inconvenience of the whole Kingdom is the maximum inconvenience among its cities.

You are given int[]s citiesX and citiesY, where (citiesX[i], citiesY[i]) are the coordinates of the i-th city.The 0-th city is the capital. Distribute teleportCount teleports in such a way that minimizes the inconvenience of the Kingdom and return that minimum inconvenience value.