ykmakuのブログ

競技プログラミングをがんばるブログ

ARC 088 E - Papple Sort

  • 問題

beta.atcoder.jp

  • 解法

回文は各アルファベットに対して左半分と右半分でそのアルファベットが出てくる回数が同じである。
以下の場合は回文にすることはできない。

  • Sにおいて奇数回現れる文字が2種類以上
  • Sにおいて奇数回現れる文字が1種類かつ|S|が偶数
  • Sにおいて奇数回現れる文字が0種類かつ|S|が奇数

以上のいずれの条件も満たさないときは以下のようにしてSから回文を作ることができる。
まずSの各文字が左半分か中央(|S|が奇数のときのみ)、右半分のどこに属するのかを決める。これは例えばSにaが5回出てくるなら1個めと2個めは左半分、3個めは中央、残りは右半分とすれば良い。(sample2なら"ataatmma"→"atamatma")
この操作を行ったあと、右半分を左半分の文字列を反転させたものと同じになるようにswapしていく。("atam atma"→"atam mata")

出来上がった回文の各文字がSのどこにあったのかを記憶しておけばバブルソートの交換回数を求める要領で必要な操作回数が求められる。
(sample2なら"ataatmma(12345678)" → "atammata(12367458)"なので12367458に対するバブルソートの交換回数を求めれば良い。)

#include <iostream>
#include <string>
#include <vector>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

struct BIT{
    ll N;
    vector<ll> bit;
    BIT(ll N) : bit(N+1),N(N){};

    ll sum(ll i){
        ll s = 0;
        while(i>0){
           s += bit[i];
           i -= i& -i;
        }
        return s;
    }

    void add(ll i,ll x){
        while(i <= N){
            bit[i] += x;
            i += i & -i;
        }
    }
};

//反転数を求める
ll inverse_number(vector<ll> z){
    ll n = z.size();
    ll inv_num = 0;

    BIT b(n);
    for(ll i = 0; i <= n; i++){
        b.bit[i] = 0;
    }

    for(ll i = 0; i < n; i++){
        inv_num += i - b.sum(z[i]);
        b.add(z[i],1);
    }

    return inv_num;
}

int main()
{
	string s;
	cin >> s;

	ll n = s.length();
	vector<vector<ll> > al_pos(26);  //initial position

	for(ll i = 0; i < n; i++){
		al_pos[s[i]-'a'].push_back(i);
	}

	ll odd_al = -1;
	for(ll i = 0; i < 26; i++){
		if(al_pos[i].size() % 2 != 0){
			if(odd_al >= 0){
				cout << -1 << endl;
				return 0;
			}else{
				odd_al = i;
			}
		}
	}

	if((odd_al>=0 && n%2==0) || (odd_al<0 && n%2!=0)){
		cout << -1 << endl;
		return 0;
	}

	ll al_now[26] = {0};

	string front,back,center;
	for(ll i = 0; i < n; i++){
		if(n%2!=0 && al_now[s[i]-'a'] == al_pos[odd_al].size()/2 && s[i]-'a' == odd_al){
			center.push_back(s[i]);
			al_now[s[i]-'a']++;
		}else if(al_now[s[i]-'a']+1<= al_pos[s[i]-'a'].size() / 2){
			front.push_back(s[i]);
			al_now[s[i]-'a']++;
		}else{
			back.push_back(s[i]);
			al_now[s[i]-'a']++;
		}
	}

	for(ll i = 0; i < 26; i++) al_now[i]=0;

	vector<ll> kaibun_index; //回文にしたあとのindex
	for(ll i = 0; i < front.length(); i++){
		kaibun_index.push_back(al_pos[front[i]-'a'][al_now[front[i]-'a']]);
		al_now[front[i]-'a']++;
	}
	for(ll i = 0; i < center.length(); i++){
		kaibun_index.push_back(al_pos[center[i]-'a'][al_now[center[i]-'a']]);
		al_now[center[i]-'a']++;
	}
	for(ll i = front.length()-1; i >= 0; i--){
		kaibun_index.push_back(al_pos[front[i]-'a'][al_now[front[i]-'a']]);
		al_now[front[i]-'a']++;
	}

	for(ll i = 0; i < n; i++) kaibun_index[i]++;

	cout << inverse_number(kaibun_index) << endl;

	return 0;
}