GCJ 2016 Round 1A A: The Last Word

解法

S[0]〜S[N-1] を並び替えるとき、S[0]から見て外側にあるほどS[i]のiは大きくなる。ちゃんと書くと、最終的な単語の先頭部分 S[i]S[j]S[k]...S[0] においてi>j>k>...>0 が成り立たなければならない。同様に末尾のS[0]S[l]S[m]...においては0

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

string solve(const string &S) {
  vector<char> prefix, suffix;
  prefix.push_back(S[0]);
  for (int i = 1; i < S.size(); ++i)
    if (S[i] >= prefix.back())
      prefix.push_back(S[i]);
    else
      suffix.push_back(S[i]);
  reverse(prefix.begin(), prefix.end());
  string p(prefix.begin(),prefix.end());
  string s(suffix.begin(),suffix.end());
  return (p + s);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int T;
  cin >> T;
  for (int testcase = 1; testcase <= T; ++testcase) {
    string S;
    cin >> S;
    string ans = solve(S);
    cout << "Case #" << testcase << ": ";
    cout << ans << endl;
  }
}