TopCoder SRM 432 DIV 2

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

500は発想の転換だった・・・終わったあと@phyllo とあーだこーだ考えていたらできた。いい問題だった

Problem 250 GroupedWordChecker

問題

A word is grouped if, for each letter in the word, all occurrences of that letter form exactly one consecutive sequence. In other words, no two equal letters are separated by one or more letters that are different. For example, the words "ccazzzzbb" and "code" are grouped, while "aabbbccb" and "topcoder" are not.

You are given several words as a String[]. Return how many of them are grouped.

http://www.topcoder.com/stat?c=problem_statement&pm=10295&rd=13694

My code

bool inRange(int a,int min, int max){ return min<=a && a<max; };

bool isGroup(string s){
	for(int i=0 ; i<s.size() ; i++){
		int phase = 0;
		for(int j=i+1 ; j<s.size() ; j++){
			if(phase==0 && s[i]!=s[j]) phase = 1;
			if(phase==1 && s[i]==s[j]) phase = 2;
		}

		if(phase ==2) return false;
	}
	return true;
}

class GroupedWordChecker {
public:
  int howMany(vector <string> words) {
    int result=0;

	for(int i=0 ; i<words.size() ; i++){
		if(isGroup(words[i])) result++;
	}

    return result;
  }
};

Problem 500 LampsGrid

問題

Jack has bought a rectangular table containing a grid of lamps. Each lamp is initially either "on" or "off". There is a switch underneath each column, and when the switch is flipped, all the lamps in that column reverse their states ("on" lamps become "off" and vice versa).

A row in the grid is considered lit if all the lamps in that row are "on". Jack must make exactly K flips. The K flips do not necessarily have to be performed on K distinct switches. His goal is to have as many lit rows as possible after making those flips.

You are given a String[] initial, where the j-th character of the i-th element is '1' (one) if the lamp in row i, column j is initially "on", and '0' (zero) otherwise. Return the maximal number of rows that can be lit after performing exactly K flips.

http://www.topcoder.com/stat?c=problem_statement&pm=10154&rd=13694

解説

Sooner or later you should notice one very important fact: all equal rows remain equal after any number of flips. So, if some row is lit at any moment, all initially equal rows will be lit as well and all other rows will not be lit. Therefore, the solution is to try for each row to make lit, and if it is possible, count the number of rows equal to this one and choose among such rows one with the maximal number of equal rows.

How to check if the given row can be lit after exactly K flips ? Note that the order of flips doesn't affect on the final result. Also, making 2 flips in the same column doesn't change row at all. Suppose we have M "off" lamps in this row. To be able to switch all these lamps to the "on" state we need exactly M flips. So, K should be no less than M. Now, if (K-M) is even, we can flip always the first column and at the end the row will be lit. If (K-M) is odd, it's impossible to lit this row after exactly (K-M) flips.

http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm432

My code

int KK;
int rowcnt(vector<string> v){
	int cnt=0; 
	bool isAll;

	for(int i=0 ; i<(signed)v.size() ; i++){
		isAll = true;

		for(int j=0 ; j<(signed)v[0].size() ; j++){
			if(v[i][j]=='0'){
				isAll = false;
				break;
			}
		}
		if(isAll) cnt++;
	}
	return cnt;
}

vector<string> switchColumn(vector<string> v, int col){
	for(int i=0 ; i<(signed)v.size() ; i++){
		if(v[i][col]=='0') v[i][col]='1';
		else v[i][col]='0';
	}
	return v;
}

int changes(vector<string> v, string s){
	vector<int> a[50];

	int cnt=0;
	for(int i=0 ; i<(signed)s.size() ; i++){
		if(s[i]=='0'){
			v = switchColumn(v,i);
			cnt++;
		}
	}
	if(cnt > KK || cnt%2!=KK%2) return 0;
	return rowcnt(v);
}

int define(vector<string> v){
	int tmp, maxcnt=0;
	for(int i=0 ; i<(signed)v.size() ; i++){
		tmp = changes(v, v[i]);
		maxcnt = max(maxcnt, tmp);
	}
	return maxcnt;
}

class LampsGrid {
public:
  int mostLit(vector <string> initial, int K) {
    int result=0;

	KK = K;
	vector<string> v = initial;
	
	int tmp, maxcnt=0;
	for(int i=0 ; i<(signed)v.size() ; i++){
		tmp = changes(v, v[i]);
		maxcnt = max(maxcnt, tmp);
	}

	return maxcnt;
  }
};

Problem 1000 TreesDivision

問題

>http://www.topcoder.com/stat?c=problem_statement&pm=9873&rd=13694>
Two brothers have a garden containing several profitable fruit trees. The garden can be represented as a plane, where each tree is a point. The brothers have decided to divide the garden into two parts using a straight line. No trees must lie on that line. One brother will then receive all the income from the trees on one side of the line, and the other brother will receive all the income from the trees on the other side of the line.

You are given int[]s x, y and income, where (x[i], y[i]) are the coordinates of the i-th tree, and income[i] is the annual income generated by the i-th tree. Return the minimal possible absolute difference between the total annual incomes of the brothers.