TopCoder SRM 424 DIV 2

Problem	Check	Points
250	○	243.10
500	×	-
900	-	-

終わったあと900を解いてみようとしたのですが、全くわからず・・・@phyllo さんと @Matsu4512 さんに全域木を探すための手法、プリム法を丁寧に教えてもらいました。次にちゃんと活かしたい。

TopCoder Statistics: SRM 424 Problem Set & Analysis

Problem 250 MagicSpell

問題

You are given a String spell containing an ancient magic spell. The spell is encrypted, but the cypher is quite simple. To decrypt the spell, you need to find all occurrences of the letters 'A' and 'Z', and then reverse their order. For example, if the encrypted spell is "AABZCADZA", you would first find all the 'A's and 'Z's: "AA_Z_A_ZA". You would then reverse their order: "AZ_A_Z_AA". The final decrypted spell is "AZBACZDAA". Return the decrypted version of the given spell.

http://www.topcoder.com/stat?c=problem_statement&pm=10176&rd=13515

My code

class MagicSpell {
public:
  string fixTheSpell(string spell) {
	deque<char> c;

	for(int i=0 ; i<spell.size() ; i++){
		if(spell[i] == 'A' || spell[i] == 'Z'){
			c.push_back(spell[i]);
			spell[i] = 0;
		}
	}

	for(int i=0 ; i<spell.size() ; i++){
		if(spell[i]==0){
			spell[i] = c.back();
			c.pop_back();
		}
	}
    return spell;
  }
};

Problem 500 ProductOfDigits

問題

You are given an int N. Find the smallest positive integer X such that the product of its digits (in decimal notation) is equal to N. Return the number of digits in X, or return -1 if such a number does not exist.

http://www.topcoder.com/stat?c=problem_statement&pm=10177&rd=13515

My code

deque<int> integerDigits(int x){
	deque<int> arr;
	while(x!=0){
		arr.push_front(x%10);
		x/=10;
	}
	return arr;
}

vector<int> factorize(int n){

	vector<int> primes;
	int tmp1;
	int a=2;

	while(1){
		while(1){
			tmp1 = n%a;

			if(tmp1==0){
				 n /= a;
				 primes.push_back(a);
			}
			else break;
		}
		if(n==1) break;
		a++;
		if(a>10){
			primes.clear();
			primes.push_back(100);
			return primes;
		}
	}
	return primes;
}


class ProductOfDigits {
public:
  int smallestNumber(int N) {


	  if(N==1) return 1;
	  vector<int> v = factorize(N);

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

	  if(v.size()>0 && v[v.size()-1]>=10) return -1;

	  for(int k=0 ; k<1000 ; k++){
		  for(int i=1; i<v.size() ; i++){
			  if(v[0]*v[i] < 10){
				  v[0] = v[0]*v[i];
				  v[i] = 100;
			  }
		  }
		  sort(v.begin(), v.end());
	  }

	  int cnt = 0;
	  for(int i=0 ; i<v.size() ; i++){
		  if(v[i]!=100) cnt++;
	  }
	  return cnt;
    }
};

Problem 900 BestRoads

問題

There are N cities numbered 0 to N-1. The j-th character of the i-th element of roads is 'Y' if there is a bidirectional road between cities i and j, and 'N' otherwise.

The road connecting cities A and B, where A < B, has a higher priority than the road connecting cities C and D, where C < D, if either A < C or (A = C and B < D). A set of roads is a list of one or more roads sorted from highest to lowest priority. A set S1 has a higher priority than set S2 if road S1[i] has a higher priority than road S2[i], where i is the earliest index at which the two sets differ. A set of roads is called connected if there's a path between any pair of cities containing only the roads from this set.

Your task is to find the connected set with the highest priority containing exactly M roads. Return a int where the i-th element is the number of roads in that set containing city i as an endpoint. Return an empty int if there is no such set.

My code

int size;
int r[100][100];
int a[100][100];
int mincost[100];
bool used[100];
int minedge[100];
int INF = 1000000;

bool inRange(int x){return 0<= x && x < size;}

vector<int> calc(void){
	vector<int> v;
	v.clear();

	for(int i=0 ; i<size ; i++){
		int cnt = 0;
		for(int j=0 ; j<size ; j++){
			if(a[i][j]==1) cnt++;
		}
		v.push_back(cnt);
	}
	return v;
}


int prim(){
	for(int i=0 ; i<size ; i++){
		mincost[i] = INF;
		used[i] = false;
		minedge[i] = -1;
	}
	mincost[0] = 0;
	int res = 0;

	while(true){
		int v = -1;

		// まだ使われていない頂点の中からコストが最小になるものを探す
		for(int u=0 ; u<size ; u++){
			if(!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u;
		}

		if(v == -1) break;
		used[v] = true;
		if(inRange(v) && inRange(minedge[v])){
			a[v][minedge[v]] = 1;
			a[minedge[v]][v] = 1;
			cout << v << " " << minedge[v] << endl;
			res++;
		}

		for(int u=0 ; u<size ; u++){
			if(!used[u] && mincost[u] > r[v][u]){
				mincost[u] = r[v][u];
				minedge[u] = v;
			}
		}
	}
	return res;
}


class BestRoads {
public:
  vector <int> numberOfRoads(vector <string> roads, int M) {
	size = roads.size();

	int cnt=1;
	for(int i=0 ; i<size ; i++){
		for(int j=i ; j<size ; j++){
			if(roads[i][j]=='Y'){
				r[i][j] = cnt;
				r[j][i] = cnt++;
			}
			else{
				r[i][j] = INF;
				r[j][i] = INF;
			}
			a[i][j] = 0;
			a[j][i] = 0;
		}
	}

	
	int p = prim();
	cout << p << endl;
	if(p != size-1) return vector<int>();

	for(int i=0 ; i<size; i++){
		for(int j=i+1 ; j<size ; j++){
			if(r[i][j]>0 && r[i][j]!=INF && a[i][j]==0){
				a[i][j] = 1;
				a[j][i] = 1;
				p++;
			}
			if(p==M) break;
		}
		if(p==M) break;
	}

	if(p<M) return vector<int>();
	return calc();

  }
};