TopCoder SRM 386 DIV 2

Problem	Check	Points
250	o	244.94
500	o	201.94
1000	-	-

前回に引き続き、正解率の低いMediumを倒せた！調子いいじゃなイカ！

TopCoder Statistics

@uwitenpen
@phyllo 250 500

Problem 250 TrophyShelf

You have several trophies sitting on a shelf in a straight line. Their heights are given in a int trophies, from left to right. The shelf is positioned so that whenever people enter your room, they see it directly from the left side. In other words, the leftmost trophy is completely visible to the viewer, the next trophy in line is directly behind it, and so on.

Unfortunately, tall trophies near the left side of the shelf might block the view of other trophies. A trophy is visible only if every trophy in front of it (from the viewer's perspective) is strictly shorter than it is. You wonder if rotating the shelf 180 degrees would increase the number of visible trophies.

Return a int containing exactly two elements. The first element should be the number of trophies visible when viewing the shelf directly from the left side, and the second element should be the number of trophies visible when viewing the shelf directly from the right side.

class TrophyShelf {
public:
  vector <int> countVisible(vector <int> trophies) {

	  int a1=0;
	  int tmp=0;
	  for(int i=0 ; i<trophies.size() ; i++){
		  if(tmp < trophies[i]){
			  a1++;
			  tmp = trophies[i];
		  }
	  }

	  tmp=0;

	  int a2=0;
	  for(int i=trophies.size()-1 ; i>=0 ; i--){
		  if(tmp < trophies[i]){
			  a2++;
			  tmp = trophies[i];
		  }
	  }
	  vector<int> v;
	  v.push_back(a1);
	  v.push_back(a2);

	  return v;
  }
};

Problem 500 CandidateKeys

A database table consists of a set of columns called attributes, and a set of rows called entries. A superkey is a set of attributes such that each entry's values for those attributes forms a unique ordered set. That is, for any superkey, each pair of entries differs in at least one of the attributes contained within the superkey. A candidate superkey is a superkey such that no proper subset of its attributes forms a superkey.

Return a int with exactly two elements. The first element should be the number of attributes in the smallest candidate superkey of the table, and the second element should be the number of attributes in the largest candidate superkey of the table. If there is no valid candidate superkey, return an empty int instead.

The input is described by a String[] table. Each String in table represents one entry, while characters contained in the String are attribute values for that entry.

かなり分かりづらい問題文。superkeyとcandidate superkeyの定義の理解がカギ。candidate superkeyについては、isSuperkey関数ができたらすんなり作れた。

string intToBitString(int n, int dig){
	string s;

	int a = dig-1;
	while(a>=0){
		if((n & 1<<a) == 1<<a) s += "1";
		else s += "0";
		a--;
	}

	return s;
}

vector<string> t;
int entry, attribute;


int countOne(string s){
	int cnt=0;
	for(int i=0 ; i<(signed)s.size() ; i++){
		if(s[i]=='1') cnt++;
	}
	return cnt;
}

bool isSuperset(string s){
	set<string> ss;

	string tmp;
	for(int i=0 ; i<entry ; i++){
		tmp = "";
		for(int j=0 ; j<attribute ; j++){
			if(s[j]=='1') tmp += t[i][j];
		}
		ss.insert(tmp);
	}

	if(ss.size()!=entry) return false;
	else return true;
}

bool isCandidateSuperset(string s){
	if(!isSuperset(s)) return false;

	if(countOne(s)==1) return true;

	string s2 = s;

	for(int i=0 ; i<(signed)s.size() ; i++){
		if(s[i]=='1'){
			s2[i] = '0';
			if(isSuperset(s2)) return false;
			s2[i] = '1';
		}
	}
	return true;
}

class CandidateKeys {
public:
  vector <int> getKeys(vector <string> table) {
	  entry = table.size();
	  attribute = table[0].size();

	  t = table;

	  int maxn = 0;
	  int minn = 999;

	  for(int i=1 ; i< (1<<attribute) ; i++){
		  string s = intToBitString(i,attribute);

		  if(isCandidateSuperset(s)){
			  maxn = max(maxn, countOne(s));
			  minn = min(minn, countOne(s));
		  }
	  }

	  if(maxn==0) return vector<int>();
	  vector<int> ans;
	  ans.push_back(minn);
	  ans.push_back(maxn);
	  return ans;
  }
};