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;
}