Single Round Match 437 (Div2/500point)

「整数nを10進法表記にして、k回数字の入れ替えを行ってつくることのできる最大の値は何か」という問題。ただし0で始まる数字を作ってはいけない。それが避けられない場合は-1を返せ、とのこと。

for文で前置インクリメントを使ってないのはよくないな。あと最後で最大の値を検索しているけど、setはソートされてるんじゃないのか。

coding time: 0:26:30.942, Passed System Test, 305.56 points

vector<int> to_vec(int n){
  vector<int> result;
  while(n){
    result.insert(result.begin(), n % 10);
    n /= 10;
  }
  
  return result;
}

vector<int> swap(vector<int> n, int i, int j){
  // n is a copy
  swap(n[i], n[j]);
  return n;
}

int to_int(vector<int> xs){
  int result = 0;
  for(size_t i=0; i < xs.size(); i++){
    result = result * 10 + xs[i];
  }
  return result;
}

class TheSwap {
public:
  int findMax(int n, int k) {
    vector<int> xs = to_vec(n);
    size_t N = xs.size();
    if(N == 1) return -1;
    set<int> cur;
    cur.insert(n);
    set<int> next;
    typedef set<int>::iterator siter;
    for(size_t times=0; times < k; times++){
      for(siter iter=cur.begin(), end=cur.end(); iter != end; iter++){
	int n = *iter;
	vector<int> xs = to_vec(n);
	for(size_t i=0; i<N; i++){
	  for(size_t j=i+1; j<N; j++){
	    vector<int> new_xs = swap(xs, i, j);
	    if(new_xs[0] != 0){
	      next.insert(to_int(new_xs));
	    }
	  }
	}
      }
      if(next.empty()) return -1;
      cur = next;
      next.clear();
    }
    int result = 0;
    for(siter iter=cur.begin(), end=cur.end(); iter != end; iter++){
      if(*iter > result){
	result = *iter;
      }
    }
    return result;
  }
}