TopCoder SRM 459 DIV 2

Problem 500

// -inf to 0
int bottom;

// area[k] -> k to k+1
int area[1001];
int point[1001];

vector<string> split(const string& str, const string& delimiter) {
    // delimiter(2 文字以上も可) を空白に置換
    string item(str);    
    for(unsigned pos = item.find(delimiter); pos != string::npos; pos = item.find(delimiter, pos)) {
        item.replace(pos, delimiter.size(), " ");
    }
    // 分解
    stringstream buf(item);

    // 読み取り
    vector<string> result;
    while(buf >> item) {
        result.push_back(item);
    }

    return result;
}



class Inequalities {
public:
  int maximumSubset(vector <string> inequalities) {

	  for(int i=0 ; i<= 1000 ; i++){
		  area[i] = point[i] = 0;
	  }
	  bottom = 0;

	  for(int i=0 ; i<inequalities.size() ; i++){
		 vector<string> vs = split( inequalities[i], ",");

		 int p = atoi(vs[2].c_str());

		 if( vs[1] == "=" ){
			 point[p]++;
		 }

		 else if( vs[1] == ">=" ){
			 for(int j=p ; j<=1000 ; j++){
				 point[j]++;
				 area[j]++;
			 }
		 }
		 else if( vs[1] == "<=" ){
			 bottom+=1;

			 point[p]++;
			 for(int j=p-1 ; j>=0 ; j--){
				 point[j]++;
				 area[j]++;
			 }

		 }

		 else if( vs[1] == ">"){
			 area[p]++;
			 for(int j=p+1 ; j<=1000 ; j++){
				 point[j]++;
				 area[j]++;
			 }
		 }
		 else{
			 bottom++;
			 for(int j=p-1 ; j>=0 ; j--){
				 point[j]++;
				 area[j]++;
			 }
		 }
	  }

	  int maxp=0;
	  for(int i=0 ; i<=1000 ; i++){
		  maxp = max( maxp, max( point[i], area[i] ));
	  }

	  return max( maxp, bottom );

  }
};

Problem 1000

double dpa[51][51];
double dpb[51][51];

int num1[51];

class ParkAmusement {
public:
  double getProbability(vector <string> landings, int startLanding, int K) {
    double result;

	for(int i=0 ; i<51 ; i++){
		for(int j=0 ; j<51 ; j++){
			dpa[i][j] = dpb[i][j] = 0;
		}
	}

	for(int i=0 ; i<landings.size() ; i++) dpa[0][i] = 1;
	dpb[0][startLanding] = 1;


	for(int i=0 ; i<landings.size() ; i++){
		int a=0;
		for(int j=0 ; j<landings.size() ; j++){
			if( landings[i][j] == '1') a++;
		}
		num1[i] = a;
	}

	for(int i=0 ; i<K ; i++){
		for(int j=0 ; j<landings.size() ; j++){
			if( num1[j] == 0 ) continue;

			for(int k=0 ; k<landings.size() ; k++){
				if(landings[j][k] == '1'){
					dpa[i+1][k] += dpa[i][j]/num1[j];
					dpb[i+1][k] += dpb[i][j]/num1[j];
				}
			}
		}
	}

	double numerator = 0, denominator = 0;

	for(int i=0 ; i<landings.size() ; i++){
		if( landings[i][i] == 'E' ){
			numerator += dpb[K][i];
			denominator += dpa[K][i];
		}
	}

    return numerator/denominator;
  }
};