2017-12-30

ARC 088 E - Papple Sort

#競プロ

解説

E - Papple Sort

公式解説が賢かった（レート1600並感）。

問題概要

英小文字からなる文字列 S が与えられる。隣り合う 2 つの文字をスワップできる。 S を回文にするためのスワップの最小回数を求める。回文にできない場合は −1 を出力する。

考察

回文なので、文字列を半分に分けて考えそう。
左右どちらの文字列に合わせて回文にすれば良いのかわからない。
外側から貪欲に決めれば最小回数になりそう（適当）

外側から決める方法

以下、スワップする回数をコストと呼ぶ。

回文；????????
余り；ataatmma

回文を a??????a にするとき、必要なコストは0。回文を t??????t にするとき、必要なコストは4。回文を m??????m にするとき、必要なコストは6。よって、a??????a にするのが最善。

回文：a??????a
余り：taatmm

同様に、 aa????aa にするとき、コスト4。 at????ta にするとき、コスト2。 am????ma にするとき、コスト4。よって、at????ta にするのが最善。

これを繰り返す。

回文：at????ta
余り：aamm

回文：ata??ata
余り：mm

回文：atammata
余り：

計算量

外側の文字を決める O(26)
外側を決めうちしたとき、必要なコストを求める O(log |S|)

各英小文字につき、何番目に出てくるかを前計算しておき、最も小さい値と最も大きい値（外側に近い）を参照すればよい（前計算 O(|S|)、本計算O(1)）。ただし、「余り」文字列において何番目に現れたかを持っていなければ、コストが計算できない。そのため、セグ木（BIT）を使って何番目かを再計算する必要がある。よって、O(log |S|)となる。

回文を構築する O(|S|)

したがって、O(26 * |S| log |S|)

実装

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
const int INF = 1e8;
using namespace std;

const int MAX_N = 200005;

//[1, n]
int bit[MAX_N + 1] = {0};

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

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

bool impossible(vector<vector<int>> v){
	int odd = 0;
	rep(i,26){
		if(v[i].size() % 2) odd++;
	}
	return odd >= 2;
}

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

	vector<vector<int>> v(26); // 各英小文字が何番目に現れるか
	rep(i,s.size()){
		v[s[i] - 'a'].emplace_back(i);
	}
	if(impossible(v)){
		cout << -1 << endl;
		return 0;
	}
	
	pair<int, int> p[26];
	rep(i,26) p[i] = make_pair(0, v[i].size() - 1); //front, back
	
	int len = s.size() - 1;
	long long ans = 0;
	rep(i,s.size() / 2){
		int t;
		int minCost = INF;
		rep(j,26){
			if(v[j].size() <= 1) continue;
	
			int front, back;
			tie(front, back) = p[j];
			if(front >= back) continue;
	
			int front_p = v[j][front];
			int back_p = v[j][back];
	
			int left = front_p - sum(front_p + 1); //  「余り」文字列の何番目に現れるか
			int right = back_p - sum(back_p + 1);
	
			int cost = left + (len - right); // 'a' + j を外側に移動させるコスト
			if(minCost > cost){
				minCost = cost;
				t = j;
			}
		}
	
		ans += minCost;
		add(v[t][p[t].first] + 1, 1);
		add(v[t][p[t].second] + 1, 1);
		p[t].first++;
		p[t].second--;
		len-=2;
	}
	
	cout << ans << endl;
}