TopCoder SRM 388 DIV 2

Problem	Check	Points
250	x	-
500	o	?
1000	x	-

なにも　おぼえてない

TopCoder Statistics

Problem 250 MonotoneSequence

A strictly increasing sequence is a sequence of numbers where each number is strictly greater than the previous one. A strictly decreasing sequence is a sequence where each number is strictly less than the previous one. A strictly monotone sequence is a sequence that is either strictly increasing or strictly decreasing. For example, 1, 5, 6, 10 and 9, 8, 7, 1, are strictly monotone sequences, while 1, 5, 2, 6 and 1, 2, 2, 3 are not.

Given a sequence seq, determine the length of the longest contiguous subsequence that is strictly monotone (see examples for clarifications).

class MonotoneSequence {
public:
  int longestMonotoneSequence(vector <int> seq) {
	  int maxn=1;

	  int tmp = seq[0];
	  int n=1;
	  for(int i=1 ; i<seq.size() ; i++){
		  if(tmp < seq[i]){
			  n++;
		  }
		  else{
			  maxn = max(maxn, n);
			  n = 1;
		  }
		  tmp = seq[i];
	  }

	  tmp = seq[0];
	  n=1;
	  for(int i=1 ; i<seq.size() ; i++){
		  if(tmp > seq[i]){
			  n++;
		  }
		  else{
			  maxn = max(maxn, n);
			  n = 1;
		  }
		  tmp = seq[i];
	  }

	  return maxn;
  }
};

Problem 500 VoteRigging

You have used your secret mind-reading device to find out how every voter will vote in the next election. Your mind-reading device also revealed to you that all the voters are prepared to change their vote if you pay them enough.

The ith element of votes is the number of people who were originally planning to vote for candidate i. Return the minimum number of votes that you must change to ensure that candidate 0 (your favorite) will have more votes than any other candidate.

class VoteRigging {
public:
  int minimumVotes(vector <int> votes) {
	  int n = votes[0];
	  votes[0] = 0;

	  sort(votes.begin(), votes.end(), greater<int>());

	  int cnt = 0;
	  while(n <= votes[0]){
		  votes[0]--;
		  cnt++;
		  n++;

		  sort(votes.begin(), votes.end(), greater<int>());
	  }
	  return cnt;
  }
};

Problem 1000 SmoothNumbersHard

A positive integer is said to be k-smooth if its largest prime factor is no greater than k. Compute how many positive integers less than or equal to N are k-smooth.

//素数を max まで計算する
deque<bool> p;
void calcPrime(const int max){
	for(int i=0 ; i<max+1 ; i++){
		p.push_back(true);
	}
	p[0] = false;
	p[1] = false;

	double myEnd = sqrt(double(max));
	for(int i=2 ; i < myEnd ; i++){
		for(int j=2 ; i*j<=max ; j++){
			p[i*j] = false;
		}
	}
}

const int pmax = 1001;
int cnt;
int NN, kk;

// n -> 現在の値
// a -> nの中の最大の素因数
void dfs(int n, int a){
	cnt++;

	for(int i=a ; i<=kk ; i++){
		if(n*i>NN) break;
		if(!p[i]) continue;
		dfs(n*i, i);
	}
	return;
}

class SmoothNumbersHard {
public:
  int countSmoothNumbers(int N, int k) {
	  cnt=1;
	  if(k==1) return 1;
	  if(N<=k) return N;

	  NN = N;
	  kk = k;

	  calcPrime(pmax);

	  for(int i=2; i<=k ; i++){
		  if(!p[i]) continue;
		  dfs(i,i);
	  }
	  return cnt;
  }
};