AtCoder Regular Contest 088 E - Papple Sort

問題ページ
E: Papple Sort - AtCoder Regular Contest 088 | AtCoder

解法

文字列Sに文字aが11個存在すれば左の5個は回文の左半分に属し、右の5個は回文の右半分、真ん中の1個は回分の中央に属する。同じ文字を入れ替えたとしても操作回数が減らせることはないため各文字種について見ていくことでその文字が左半分、中央、右半分のどこに属するかを決定できる。
次に左半分と右半分を回文になるように操作していくことを考える。左半分を操作することと対応する右半分を操作することは実質同じ操作であるから、右半分だけを操作するとしても最小の操作回数を達成することが出来る。したがって右半分の文字列が左半分の反転になるように操作すればよい。ある文字列S1を文字列S2に変える最小の操作回数について考える。前述したように同じ文字種を入れ替えるメリットはないことから、各文字種について前から順番に対応させいけばよい。例としてatmatからmattaにすることを考える。

atmat→matta
01234→20143

したがって、並べ替える前の文字列と並べ替えた後の回文においてどの文字をどこにもっていくべきかの1対1の対応が取れる。これはバブルソートの交換回数でありO(|S|log|S|)で計算できる。

学び

ある列Aから列Bに隣接した要素を交換することで移しかえる最小回数はO(NlogN)で求めることができる
回文をつくるときは左半分 or 右半分のどちらかを決めれば残り半分は一意に決まるんだから片方だけについて考える
同じ要素を入れ替えるメリットがない→各要素ごとに前後が入れ替わることはない

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int bit[200010], n = 200010;

//0からi-1番目までの和
int sum(int i) {
  i++;
  int s = 0;
  while(i > 0) {
    s += bit[i];
    i -= i&-i;
  }
  return s;
}

//i番目(0-index)にxを加える
void add(int i, int x) {
  i++;
  while(i <= n) {
    bit[i] += x;
    i += i&-i;
  }
}

int cnt[30], idx[30], a[200010];
deque<int> idx2[30];
signed main(void)
{
  string s;
  cin >> s;
  REP(i, s.size()) cnt[s[i]-'a']++;

  int tmp = 0;
  REP(i, 26) if(cnt[i]%2) tmp++;
  if(tmp >= 2) {
    cout << -1 << endl;
    return 0;
  }

  string t1 = "", t2 = "", t3 = "";
  REP(i, s.size()) {
    if(cnt[s[i]-'a']%2) {
      if(idx[s[i]-'a'] < cnt[s[i]-'a']/2) a[i] = 0;
      else if(idx[s[i]-'a'] == cnt[s[i]-'a']/2) a[i] = 1;
      else if(idx[s[i]-'a'] > cnt[s[i]-'a']/2) a[i] = 2;
    } else {
      if(idx[s[i]-'a'] < cnt[s[i]-'a']/2) a[i] = 0;
      else a[i] = 2;
    }
    if(a[i] == 0) t1 += s[i];
    else if(a[i] == 1) t2 += s[i];
    else t3 += s[i];
    idx[s[i]-'a']++;
  }
  reverse(ALL(t1));

  // t3をt1に合わせる
  REP(i, t1.size()) idx2[t1[i]-'a'].push_front(i+s.size()/2+!!(s.size()%2));
  VI v2;
  REP(i, t3.size()) {
    v2.PB(idx2[t3[i]-'a'].back());
    idx2[t3[i]-'a'].pop_back();
  }

  // 回文にした後で移るindex
  VI v;
  int id = 0, id2 = 0;
  REP(i, s.size()) {
    if(a[i] == 0) {
      v.PB(id++);
    } else if(a[i] == 1) {
      v.PB(s.size()/2);
    } else {
      v.PB(v2[id2++]);
    }
  }

  // vの転倒数を求める
  ll ans = 0;
  REP(i, v.size()) {
    ans += i - sum(v[i]);
    add(v[i], 1);
  }
  cout << ans << endl;

  return 0;
}

ferinの競プロ帳

競プロについてのメモ

AtCoder Regular Contest 088 E - Papple Sort

解法

学び