TopCoder SRM 485 DIV 2

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

これはひどい！最悪のスタートを切りました・・・
250 -> 問題読み間違え
500 -> 実装がこんがらがった

Problem 250 MicrowaveSelling

問題

Manao lives in a country where the prices of all goods are positive integers. He is setting up a company that sells microwaves, and needs to decide the best price at which to sell them. Recently, he heard of a new psychological discovery: the more trailing 9's a price has, the more attractive it is to the customer. For example, 9099 has two trailing 9's, and 8909 has only one trailing 9, so the first price is more attractive.
Manao knows that he can only afford to sell microwaves at a price no less than minPrice, and believes that customers will only buy the microwaves if they cost no more than maxPrice. Help Manao by finding an integer between minPrice and maxPrice, inclusive, which has the maximum possible number of trailing 9's. If there are several candidates, return the largest one.

My code

int countContinue9(int x){
	int count=0;
	
	while(x%10==9){
		count++;
		x/=10;
	}
	return count;
}

class MicrowaveSelling {
public:
  int mostAttractivePrice(int minPrice, int maxPrice) {
    int result;

	int max = 0, max9 = 0;
	for(int i=minPrice; i<=maxPrice ; i++){
		if(max9 <= countContinue9(i) ){
			max9 = countContinue9(i);
			max = i;
		}
	}
	if( max9==0 ) return maxPrice;
	else return max;
  }
};

"trail"という単語を見逃していたせいで、余計な実装をした上に間違えたという悲惨な状況に。

Problem 500 AfraidOfEven

問題

A sequence of integers a[0], a[1], ..., a[N-1], where N >= 3, is called an arithmetic progression if the difference between any two successive terms in the sequence is a constant. More precisely, it is an arithmetic progression if a[i] - a[i-1] = a[i+1] - a[i] for every integer i such that 0 < i < N-1.

Sasha and Pasha are students sharing the same room. Once, when Pasha had left the room, Sasha was in a good mood. So he took a piece of chalk and wrote an arithmetic progression on the blackboard. The progression consisted of at least 4 elements, all of which were positive integers. Then Sasha went to class, and Pasha came back.

Pasha is a very nice person, but there's one problem with him -- he's frightened of even numbers! So, when he returned, he decided to make all the numbers on the board odd. He did this by repeatedly finding an arbitrary even number X, erasing it, and writing X/2 in its place. He continued to perform this step until no even numbers remained.

Your task is to help Sasha restore the initial progression. You will be given a vector seq, where the i-th element is the i-th number in the sequence written on the blackboard after Pasha's actions. Return an vector whose i-th element is the i-th number in a sequence that Sasha could have originally written on the blackboard. The constraints will ensure that at least one such sequence exists. If there are several such sequences, choose the one among them whose vector representation is lexicographically smallest.

My code

// vが階差数列かどうかを判定する。
bool isArithProg(vector<int> v){
	int dif=v[1]-v[0];

	for(int i=0 ; i<(signed)v.size()-1 ; i++){
		if(v[i+1]-v[i] != dif) return false;
	}
	return true;
}

// a = b*2^n?
bool isTwice(int a, int b){
	while(1){
		if(a==b) return true;

		if(b%2!=0) return false;
		b/=2;
	}
}

vector<int> makeArithProg(vector<int> v, int dif, int buf){
	vector<int> empv;
	int k;

	// even-th 2x
	if(buf==0){
		for(int i=1 ; i<v.size() ; i+=2){
			k = v[i-1]+dif;
			if(isTwice(v[i], k)) v[i] = k;
			else return empv;
		}
	}

	// odd-th 2x
	if(buf==1){
		for(int i=0 ; i<v.size()-1 ; i+=2){
			k = v[i+1]-dif;
			if(isTwice(v[i], k)) v[i] = k;
			else return empv;
		}

		if(v.size()%2==1){
			k = v[v.size()-2]+dif;
			if(isTwice(v[v.size()-1], k)) v[v.size()-1] = k;
			else return empv;
		}
	}
	return v;
}

class AfraidOfEven {
public:
  vector <int> restoreProgression(vector <int> seq) {
    vector <int> result;



	if(isArithProg(seq)) return seq;
	
	vector<int> v1, v2, subv;


	for(int i=0 ; i<(signed)seq.size() ; i+=2){
		subv.push_back(seq[i]);
	}

	// 偶数番目を2倍していく
	if(isArithProg(subv) && (subv[1] - subv[0])%2==0){
		int k = (subv[1]-subv[0])/2;
		cout << "k1 -> " << k << endl;

		v1 = makeArithProg(seq, k, 0);
	}

	subv.clear();

	for(int i=1 ; i<(signed)seq.size() ; i+=2){
		subv.push_back(seq[i]);
	}

	// 奇数番目を2倍していく
	if(isArithProg(subv) && (subv[1] - subv[0])%2==0){
		int k = (subv[1]-subv[0])/2;
		cout << "k2 -> " << k << endl;

		v2 = makeArithProg(seq, k, 1);
	}
	
	if(v2.empty()) return v1;
	else if(v1.empty()) return v2;
	else{
		for(int i=0 ; i<(signed)v1.size() ; i++){
			if(v1[i] < v2[i]) return v1;
			if(v1[i] > v2[i]) return v2;
		}
		return v1;
	}
  }
};

全探索でない方法を思いついたのは良かったけど、時間内に解けなくちゃ意味が無いよ・・・
終了後は落ち着いたせいか、(これでもかなり)すっきりしたコードになった。

Problem 1000 RectangeAvoidingColoringEasy

問題

There is an N x M board divided into 1 x 1 cells. The rows of the board are numbered from 0 to N-1, and the columns are numbered from 0 to M-1. The cell located in row r and column c has coordinates (r, c).

In a coloring of the board, each cell on the board is colored white or black. A coloring is called rectangle-avoiding if it is impossible to choose 4 distinct cells of the same color so that their centers form a rectangle whose sides are parallel to the sides of the board. In other words, a coloring is rectangle-avoiding if, for each a, b, c, and d with 0 <= a < b < N, 0 <= c < d < M, there is at least one white cell and at least one black cell among the cells (a, c), (a, d), (b, c) and (b, d).

You are given a vector board representing a board. The j-th character of the i-th element of board represents cell (i, j), and it can be 'W', 'B' or '?'. Here, 'W' indicates a white cell, 'B' indicates a black cell and '?' indicates an uncolored cell. For each uncolored cell, you may choose to color it either white or black. Return the number of different rectangle-avoiding colorings that can be achieved. If it is impossible to achieve a rectangle-avoiding coloring, return 0.