TopCoder SRM 458 DIV 2

Problem 500

int n;

// int aの下からn桁分のbitをdequeに入れて返す
deque<int> bitDigits(int a, int dig){
	deque<int> arr;

	for(int i=0 ; i<dig ; i++){
		arr.push_front(a%2);
		a/=2;
	}
	return arr;
}


class BouncingBalls {
public:
  double expectedBounces(vector <int> x, int T) {
    double result;
	n = x.size();

	ll time = 2LL*T;

	double ans=0;

	sort(x.begin(), x.end());

	for(int i=0 ; i< (1<<n) ; i++){
		deque<int> d = bitDigits(i, n);
		
		int cnt=0;

		for(int j=0 ; j<d.size() ; j++){
			int p = d[j];
			int pnum = x[j];

			
			if(p == 0){
				for(int k=j-1 ; k>=0 ; k--){
					if( d[k] == 1 && pnum - x[k] <= time ) cnt++;
				};
			}
			else{
				for(int k=j+1 ; k<d.size() ; k++){
					if( d[k] == 0 && x[k] - pnum <= time ) cnt++;
				};
			}
			
		}
	
		ans += (double)cnt/2;

	}

    return ans/(1<<n);
  }
};

Problem 950

これ絶対950じゃねぇよ

ll calc(int x, int y1, int y2, int z1, int z2){
	z1 = max(z1, x*x+1);

	if(z2 < z1 ) return 0;

	ll a1 = min( (ll)y2, (ll)floor( (double)z2/x ) );
	ll a2 = max( (ll)y1, (ll)ceil(  (double)z1/x ) );
	a2 = max( a2, (ll)x );

	return max(0LL, a1-a2+1);
}


class ProductTriplet {
public:
  long long countTriplets(int minx, int maxx, int miny, int maxy, int minz, int maxz) {
	ll ans = 0;

	for(ll x=minx ; x*x < maxz && x<=maxx ; x++){
		ans += calc(x, miny, maxy, minz, maxz );
	}

	for(ll y=miny ; y*y < maxz && y<=maxy ; y++){
		ans += calc(y, minx, maxx, minz, maxz );
	}

	for(ll a = max(minx,miny) ; a*a <= maxz && a<= min(maxx, maxy) ; a++){
		if(minz <= a*a) ans++;
	}
	return ans;
  }
};