TopCoder SRM 413 DIV 2

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

点数的にはひどいものだったけど、今日は@uwitenpen さんのコードを見てすごく勉強になりました。ていうか500と1000はほとんどuwiさんのパクリです！

・再帰が間に合わないときはメモ化
・メモ化は別に全部しなくてもいい

TopCoder Statistics: SRM 413 Problem Set & Analysis

Problem 250 Subway2

問題

Subway trains can move people quickly from one station to the next. It is known that the distance between two consecutive stations is length meters. For safety, the train can't move faster than maxVelocity meters/sec. For comfort, the absolute acceleration can't be larger than maxAcceleration meters/sec^2. The train starts with velocity 0 meters/sec, and it must stop at the next station (i.e., arrive there with a velocity of 0 meters/sec). Return the minimal possible time to get to the next station.

My code

class Subway2 {
public:
  double minTime(int length, int maxAcceleration, int maxVelocity) {
	  double dlength = ((double)length)/2;
	  double a=maxAcceleration;
	  
	  double time1 = sqrt(2*dlength/a);
	  if(time1*a < maxVelocity) return time1*2;

	  time1 = maxVelocity/a;
	  double time2 = dlength/(double)maxVelocity - time1/2;
	  
	  return (time1+time2)*2;
  }
};

Problem 500 ArithmeticProgression

問題

In mathematics, an arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference of any two successive members of the sequence is a constant. For instance, the sequence 3, 5, 7, 9, 11, 13... is an arithmetic progression with common difference 2. An arithmetic sequence can always be represented as an=a0+n*d.

You will be given a sequence seq, where seqi = [ai+1] for some nondecreasing arithmetic sequence a (both indices are 0-based). [x] denotes the floor function (see Notes). The sequence a is defined as a0+i*d. Return the minimal possible value for d. If no possible value exists for d, return -1 instead.

My code

class ArithmeticProgression {
public:
  double minCommonDifference(int a0, vector <int> seq) {
	  if(seq.size()==0) return (double)0;

	  double l = 0, r = 10000000, a, b;
	  for(int i=0 ; i<seq.size() ; i++){
		  a = (double)(seq[i]-a0)  /(i+1);
		  b = (double)(seq[i]-a0+1)/(i+1);

		  if(l<a) l=a;
		  if(b<r) r=b;
	  }

	  if(r-l >= 1E-9) return l;
	  else return -1;
  }
};

Problem 1000 InfiniteSequence

問題

Let's consider an infinite sequence A defined as follows:

• A0 = 1;
• Ai = A[i/p] + A[i/q] for all i >= 1, where [x] denotes the floor function of x. (see Notes)

You will be given n, p and q. Return the n-th element of A (index is 0-based).

My code

int pp, qq;
const int N=1000000;
ll memo[N];

ll A(ll n){
	if(n==0) return 1;
	if(n<N && memo[n]!=-1) return memo[n];

	ll a = A( (ll)floor((double)n/(double)pp) ) + A( (ll)floor((double)n/(double)qq) );
	if(n<N) memo[n] = a;

	return a;
}

class InfiniteSequence {
public:
  long long calc(long long n, int p, int q) {
	  pp = p;
	  qq = q;
	  for(int i=0 ; i<N ; i++) memo[i] = -1;

	  return A(n);
  }
};