TopCoder SRM 437 DIV 2

beauty beautyうるさかったｗ

Problem 250 TheBeauty

問題

There is nothing more beautiful than just an integer number.
The beauty of an integer is the number of distinct digits it contains in decimal notation.
You are given an integer number n. Return the beauty of this number.

http://www.topcoder.com/stat?c=problem_statement&pm=10233&rd=13699

My code

// xを各桁ごとにばらしてsetに挿入する。
set<int> integerDigits(int x){
	set<int> arr;
	while(x!=0){
		arr.insert(x%10);
		x/=10;
	}
	return arr;
}

class TheBeauty {
public:
  int find(int n) {
    int result = 0;

	set<int> s = integerDigits(n);

	return s.size();
    return result;
  }
};

Problem 500 TheSwap

There is nothing more beautiful than just an integer number.

You are given an integer n. Write down n in decimal notation with no leading zeroes, and let M be the number of written digits. Perform the following operation exactly k times:

Choose two different 1-based positions, i and j, such that 1 <= i < j <= M. Swap the digits at positions i and j. This swap must not cause the resulting number to have a leading zero, i.e., if the digit at position j is zero, then i must be strictly greater than 1.
Return the maximal possible number you can get at the end of this procedure. If it's not possible to perform k operations, return -1 instead.

http://www.topcoder.com/stat?c=problem_statement&pm=10369&rd=13699

My code

// xを各桁ごとにばらしてdequeに挿入する。
deque<int> integerDigits(int x){
	deque<int> arr;
	while(x!=0){
		arr.push_front(x%10);
		x/=10;
	}
	return arr;
}

int fromDigits(deque<int> arr){
	int x=0;
	while(!arr.empty()){
		x *= 10;
		x += arr[0];
		arr.pop_front();
	}
	return x;
}

deque<int> swap(deque<int> deq, int i, int j){
	deque<int> ret;

	ret = deq;
	int tmp = ret[i];
	ret[i] = ret[j];
	ret[j] = tmp;

	return ret;
}

bool memo[1000000][10];
int maxnum;

void dfs(int n, int k){
	//cout << "n -> " << n << ",k -> "<< k << endl;
	if(k==0){
		if(maxnum < n) maxnum = n;
		return;
	}
	
	deque<int> ndeq = integerDigits(n);
	deque<int> ndeq2;
	for(int i=0 ; i<(signed)ndeq.size() ; i++){
		for(int j=i+1 ; j<(signed)ndeq.size() ; j++){

			if(i==0 && ndeq[j]==0) continue; 
			ndeq2 = swap(ndeq,i,j);

			if(!memo[fromDigits(ndeq2)][k]){
				memo[fromDigits(ndeq2)][k] = true;
				dfs(fromDigits(ndeq2), k-1);
			}

		}
	}
}

class TheSwap {
public:
  int findMax(int n, int k) {
    int result;
	maxnum = -1;
	dfs(n,k);
	return maxnum;
  }
};

DFS+メモ化ということを部長から教えてもらいました。