Codeforces Round #350 Div2 F: Restore a Number

問題

Problem - F - Codeforces

解法

含むべき部分文字列以外の部分は、残った数字でできるだけ小さい整数を作れば良い。

求めるべき文字列は3つのうちのいずれかである。
含むべき部分文字列をTとすると、

• Tを先頭に含むもの。
• Tの1桁目の数字をqとした時に、...qqqqqT... となっているもの。
• Tの1桁目の数字をqとした時に、...Tqqqqq... となっているもの。

コード

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string S, T;
  cin >> S >> T;

  vector<int> cnts(10, 0);
  for (int i = 0; i < S.size(); ++i) {
    int k = S[i] - '0';
    cnts[k]++;
  }
  for (int i = 0; i < T.size(); ++i) {
    int k = T[i] - '0';
    cnts[k]--;
  }

  for (int i = 1;; ++i) {
    string k = to_string(S.size() - i);
    int l = k.size();
    if (l == i) {
      for (int j = 0; j < k.size(); ++j) {
        cnts[k[j] - '0']--;
      }
      break;
    }
  }

  string head = "";
  vector<int> head_cnts = cnts;
  if (T[0] == '0') {
    for (int i = 1; i < 10; ++i) {
      if (head_cnts[i] > 0) {
        head.push_back(i + '0');
        head_cnts[i]--;
        break;
      }
    }
  }
  head += T;
  for (int i = 0; i < 10; ++i) {
    for (int j = 0; j < head_cnts[i]; ++j) {
      head.push_back(i + '0');
    }
  }

  vector<int> sub_head_cnts = cnts;
  string sub_head = "";
  for (int i = 1; i < 10; ++i) {
    if (sub_head_cnts[i] > 0) {
      sub_head.push_back(i + '0');
      sub_head_cnts[i]--;
      break;
    }
  }
  for (int i = 0; i < 10; ++i) {
    if (i == T[0] - '0') sub_head += T;
    for (int j = 0; j < sub_head_cnts[i]; ++j) {
      sub_head.push_back(i + '0');
    }
  }

  vector<int> sub_tail_cnts = cnts;
  string sub_tail = "";
  for (int i = 1; i < 10; ++i) {
    if (sub_tail_cnts[i] > 0) {
      sub_tail.push_back(i + '0');
      sub_tail_cnts[i]--;
      break;
    }
  }
  for (int i = 0; i < 10; ++i) {
    for (int j = 0; j < sub_tail_cnts[i]; ++j) {
      sub_tail.push_back(i + '0');
    }
    if (i == T[0] - '0') sub_tail += T;
  }

  vector<string> hoge;
  if (head[0] != '0' || head.size() == 1) hoge.push_back(head);
  if (sub_head[0] != '0' || sub_head.size() == 1) hoge.push_back(sub_head);
  if (sub_tail[0] != '0' || sub_tail.size() == 1) hoge.push_back(sub_tail);
  sort(hoge.begin(), hoge.end());
  cout << hoge[0] << endl;
}