TopCoder SRM 387 DIV 2

C++ TopCoder
Problem Check Points
250 o 242.05
600 o 199.45
1000 - -

600が解けて、僕満足！

TopCoder Statistics

@uwitenpen

Problem 250 GuessingNextElement

An integer arithmetic progression is a sequence defined by two positive integers, p and q, where p is the first element in the sequence, and all other elements are obtained by adding q to the previous element. For example, if p = 1 and q = 2, the sequence would be: 1, 3, 5, 7, ...
An integer geometric progression is a sequence defined by two positive integers, p and q, where p is the first element in the sequence, and all other elements are obtained by multiplying the previous element by q. For example, if p = 3 and q = 2, the sequence would be: 3, 6, 12, ...
You are given a vector A, which contains either an integer arithmetic or geometric progression. Determine which one it is and return the next element in the sequence. It is guaranteed that A will uniquely represent either an arithmetic or geometric progression and that result will fit in a 32-bit signed integer.

bool isArithmetic(vector<int> A){
	  ll tmp = A[1]-A[0];
	  for(int i=0 ; i<A.size()-1 ; i++){
		  if(tmp != A[i+1] - A[i]) return false;
	  }
	  return true;
}

class GuessingNextElement {
public:
  int guess(vector <int> A) {
	  if(isArithmetic(A)) return A.back()+(A[1]-A[0]);	
	  return A.back()*(A[1]/A[0]);
  }
};

Problem 600 MarblesRegroupingEasy

John is a marble collector. He keeps his marbles in boxes. He also likes to keep things in order.
One day, his younger brother was playing with the marbles. After he was done, he put all the marbles back in boxes, but he did it randomly, so certain boxes might now contain marbles of different colors. John wants him to regroup the marbles so that the grouping satisfies the following restrictions:

  • At most one box, called the joker box, may contain marbles of different colors. We can choose any box as a joker box.
  • Every box except the joker box must either be empty or only contain marbles of the same color.
  • All marbles of the same color, except those in the joker box, must be in the same box. It's possible that all marbles of the same color are in the joker box.

You are given a vector boxes, where the j-th digit of the i-th element is the number of marbles of color j in the i-th box. Return the minimal number of moves necessary to regroup the marbles, where each move consists of taking any number of marbles from one box (not necessarily of the same color) and putting them into another.

jokerを1つ決め、他の箱の物を全部jokerに移せば、条件を満たした状態になる。
これが最大になるケースで、[箱の数-1]になる。
ここから移動しなくていい数を考えると、空の箱と1つの色しか入っていない箱はもう移動しなくてもよい。ただし、例えば　


[色0だけ入っている箱][色0だけ入っている箱][JOKER]


のような場合は、[色0が入っている箱]のどちらかはjokerに移動させなければいけないので、単色の箱を、各色につき1回だけ数える。
以上より、答えは[箱の数 - 1 - 単色の箱の数(各色に付きカウントは1回だけ) - 空箱の数]。
場合によってはこの値が-1になるので、0以上となるように注意する。

int minCnt;
int box[51][51];
int m,n;


// 単色・または空の箱の数
// (単色は1つの色につき1回しかカウントしない)
int cntOnlySameBox(){
	int cnt=0; bool b;
	set<int> s;
	s.clear();

	for(int i=0 ; i<m; i++){
		int tmp=-1;
		b = true;

		for(int j=0 ; j<n ; j++){
			if(tmp==-1 && box[i][j]!=0) tmp = j;
			else if(tmp!=-1 && box[i][j]!=0){
				b = false; break;
			}
		}

		if(b){
			if(tmp==-1) cnt++;
			else s.insert(tmp);
		}
	}
	return s.size()+cnt;
}



class MarblesRegroupingEasy {
public:
  int minMoves(vector <string> boxes) {
	  m = boxes.size();
	  n = boxes[0].size();

	  for(int i=0 ; i<m ; i++){
		  for(int j=0 ; j<n ; j++){
			  box[i][j] = boxes[i][j]-48;
		  }
	  }
	  minCnt = m-1-cntOnlySameBox();

	  if(minCnt>=0) return minCnt;
	  else return 0;
  }
};