POJ 1248 Safecracker

問題

やりかた

与えられる文字列の長さはせいぜい12文字なので、全探索でも1ケースあたり程度の計算でOKなので全探索で。
ただvectorやstringを引数に関数の値渡しをすると簡単にTLEしてしまった。参照渡しにしたら簡単に通った。

以下ソース。

vector<ll> c(5);
ll calc(string &s){
  for(int i = 0; i < 5; i++) c[i] = s[i] - 'A' + 1;
  return c[0] 
    - c[1] * c[1] 
    + c[2] * c[2] * c[2]
    - c[3] * c[3] * c[3] * c[3]
    + c[4] * c[4] * c[4] * c[4] * c[4];
}

int main(int argc, char **argv){
  ll d;
  string s;
  while(cin >> d >> s){
    if(d == 0 && s == "END") break;
    sort(ALL(s));
    int L = s.length();
    string ans("AAAAA");
    string str("AAAAA");
    for(int S = 0; S < 1 << L; S++){
      if(__builtin_popcount(S) != 5) continue;
      
      int idx = 0;
      for(int i = 0; i < L; i++) if(S >> i & 1) str[idx++] = s[i];
      
      do{
	if(calc(str) == d) ans = max(ans, str);
      }while(next_permutation(ALL(str)));
    }

    if(ans == "AAAAA")	cout << "no solution" << endl;
    else		cout << ans << endl;
  }
  return 0;
}