SRM 354 Div1 Medium RemissiveSwaps

問題

整数Nが与えられる。好きな桁を2つ選んで、それらの数字を1つずつ減らしてそれらを交換するというゲームを行う。このゲームでとりうる最も大きい数字を求めよ。なおLeading Zeroができてはいけない。

やりかた

ゲーム中に桁が増えるようなことはなく、制約上Nは1000000以下なので単純なメモ化再帰で十分通る。

以下ソース。

bool vis[1000001];

class RemissiveSwaps {  
public:
  string i2s(int i){
    stringstream ss;
    ss << i;
    return ss.str();
  }
  void rec(string s){
    int L = s.length();
    int num = 0;
    for(int i = 0; i < L; i++){
      num *= 10; num += (s[i] - '0');
    }
    
    if(vis[num]) return;
    vis[num] = true;

    for(int i = 0; i < L; i++){
      if(s[i] == '0') continue; 
      for(int j = 0; j < L; j++){
	if(s[j] - s[i] >= 2){
	  s[i]--, s[j]--;
	  swap(s[i], s[j]);
	  rec(s);
	  swap(s[i], s[j]);
	  s[i]++, s[j]++;
	}
      }
    }    
    return;
  }
  int findMaximum(int N) {
    memset(vis, false, sizeof(vis));
    string s = (i2s(N));
    rec(s);
    for(int i = 1000000; i >= 0; i--) if(vis[i]) return i;
    return -1;
  }
};