提出 #70829026

---

ソースコード 拡げる

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

const int K = 26;

string solve(string s) {
  int n = s.size();
  vector<int> freq(K);
  for (char c: s) freq[c-'a']++;
  vector<int> indices(K);
  iota(indices.begin(), indices.end(), 0);
  sort(indices.begin(), indices.end(), [&] (int i, int j) {
    return freq[i] > freq[j];
  });
  if (2*freq[indices[0]]-1 <= n) {
    string t(n, ' ');
    int ptr = 0;
    for (int i = 0; i < n; i += 2) {
      t[i] = indices[ptr] + 'a';
      if (--freq[indices[ptr]] == 0) ptr++;
    }
    for (int i = 1; i < n; i += 2) {
      t[i] = indices[ptr] + 'a';
      if (--freq[indices[ptr]] == 0) ptr++;
    }
    return t;
  }

  int k = n - freq[indices[0]] + 1;
  vector<int> sizes;
  string t;
  t.reserve(n);
  int large_sz = freq[indices[0]] / k + 1;
  int small_sz = freq[indices[0]] / k;
  int num_large = freq[indices[0]] % k;
  int num_small = k - num_large;
  int leftover = -1;
  auto work = [&] (int sz, int f) {
    if (sz % 2 == 0) {
      while (f >= 2) {
        sizes.push_back(sz-1);
        sizes.push_back(sz+1);
        f -= 2;
      }
      if (f == 1) {
        leftover = sz;
      }
      return;
    }
    while (f--) {
      sizes.push_back(sz);
    }
  };
  work(large_sz, num_large);
  work(small_sz, num_small);
  if (leftover != -1) {
    sizes.push_back(leftover);
  }
  int ptr = 1;
  for (int i = 0; i < k-1; i++) {
    t += string(sizes[i], indices[0] + 'a');
    t.push_back(indices[ptr] + 'a');
    if (--freq[indices[ptr]] == 0) ptr++;
  }
  t += string(sizes[k-1], indices[0] + 'a');
  return t;
}

int main () {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int T;
  cin >> T;
  while (T--) {
    string s;
    cin >> s;
    cout << solve(s) << '\n';
  }
}

提出情報

ジャッジ結果