TopCoder SRM 489 DIV 2

Problem	Check	Points
250	○	120ぐらい
500	-	-
1000	-	-

DIV2の250が第惨事。半分ぐらいSystem Testで落とされてた。一応解けたけど、時間がかかりすぎだなー・・・

Problem 250 BadVocabulary

問題

Little Teddy and Little Tracy are now learning how to speak words. Their mother, of course, doesn't want them to speak bad words. According to her definition, a word W is bad if at least one of the following conditions hold (see the notes section for definitions):

• W contains the string badPrefix as a prefix.
• W contains the string badSuffix as a suffix.
• W contains the string badSubstring as a contiguous substring that is neither a prefix nor a suffix of W.

You are given a vector vocabulary representing the words that Teddy and Tracy are going to learn. Return the number of bad words in vocabulary.

My code

class BadVocabulary {
public:
  int count(string badPrefix, string badSuffix, string badSubstring, vector <string> vocabulary) {
	  int cnt=vocabulary.size();

	  for(int i=0 ; i<vocabulary.size() ; i++){
		  string W = vocabulary[i];

		  bool done = false;
		  if(badPrefix.size() <= W.size()){
			  string s = W.substr(0,badPrefix.size());
			  if(s==badPrefix) done = true;
		  }

		  if(badSuffix.size() <= W.size()){
			  string s = W.substr(W.size()-badSuffix.size());
			  if(s==badSuffix) done = true;
			 
		  }

		  for(int j=1 ; j+badSubstring.size() < W.size() ; j++){
			  string s = W.substr(j,badSubstring.size()); 
			  if(s==badSubstring){
				  done = true;
				  break;
			  }
		  }
		  if(!done) cnt--;
 	  }
	  return cnt;
  }
};

Problem 500 BuyingFlowers

問題

Teddy loves roses and Tracy loves lilies. They wish to plant these flowers in a large garden. However, the only florist in town sells these flowers in packets which are represented by vector s roses and lilies. The i-th packet contains roses[i] roses and lilies[i] lilies. Each packet can be bought only once. Teddy and Tracy wish to buy some flowers and arrange them into a rectangular grid. This grid must be arranged such that each cell contains exactly one flower, and any two cells which share an edge must contain different kinds of flowers. Additionally, Teddy and Tracy must use all the flowers they buy. Teddy and Tracy love square-shaped grids, so they wish to buy a set of packets such that they can arrange the flowers into the most square-like grid possible. More precisely, they wish to arrange the flowers into an R x C grid, where R and C are positive integers, such that |R-C| (|R-C| denotes the absolute value of R-C) is minimized. Return this minimum absolute value, or -1 if no valid arrangement exists.

My code

int calc(int rose, int lily){
	if(abs(rose-lily)>=2) return 99999999;

	int ans = 99999999;
	int t = rose + lily;
	
	for(int a=1 ; a<=(int)sqrt((double)t) ; a++){	
		if(t%a==0){
			ans = min(ans, abs((t/a) - a));
		}
	}
	return ans;
}

class BuyingFlowers {
public:
  int buy(vector <int> roses, vector <int> lilies) {

	int result = 99999999;
	
	for(int i=1 ; i< 1<<roses.size() ; i++){
		int r=0, l=0;

		int bit=1;
		for(int j=0 ; j<roses.size() ; j++){
			if(i&bit){
				r += roses[j];
				l += lilies[j];
			}
			bit <<= 1;
		}

		result = min(result, calc(r,l));
	}
	
	if(result!=99999999) return result;
	else return -1;
  }
};