ARC 088 E - Papple Sort
E - Papple Sort
公式解説が賢かった(レート1600並感)。
考察
- 回文なので、文字列を半分に分けて考えそう。
- 左右どちらの文字列に合わせて回文にすれば良いのかわからない。
- 外側から貪欲に決めれば最小回数になりそう(適当)
外側から決める方法
以下、スワップする回数をコストと呼ぶ。
回文;????????
余り;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
回文: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; }