#include "bits/stdc++.h"
using namespace std;
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif
using ll = long long;
int converted[100005];
int idx = 0;
long double fromleft[16][16][100005];
long double fromright[16][16][100005];
vector<vector<int>> groups;
int g;
long double calc(int amt) {
return (long double) ((long double) amt * (long double) (amt-1.0)) / 4.0;
}
long double getans(int mask, int j, int k) {
if (k >= groups[j].size()) return 1e15;
long double val = calc(k + 1) + calc((int) groups[j].size() - k - 1);
for (int i = 0; i < g; i++) {
if ((1 << i) & mask) {
val += fromleft[j][i][groups[j][k]];
if (k + 1 == groups[j].size()) continue;
val += fromright[j][i][groups[j][k+1]];
}
}
return val;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("", "r", stdin);
// freopen("", "w", stdout);
string s; cin >> s;
int n = s.size();
set<char> dup;
map<char, int> m;
for (int i = 0; i < n; i++) {
if (m.count(s[i]) != 0) {
converted[i] = m[s[i]];
} else {
m[s[i]] = m.size();
converted[i] = m[s[i]];
}
}
g = m.size();
groups.resize(g);
for (int i = 0; i < n; i++) {
groups[converted[i]].push_back(i);
}
for (int l = 0; l < g; l++) {
for (int r = 0; r < g; r++) {
long double ct = 0, res = 0;
for (int i = 0; i < n; i++) {
if (converted[i] == l) {
ct++;
} else if (converted[i] == r) {
res += ct;
fromleft[r][l][i] = res;
}
}
ct = 0, res = 0;
for (int i = n - 1; i >= 0 ; i--) {
if (converted[i] == l) {
ct++;
} else if (converted[i] == r) {
res += ct;
fromright[r][l][i] = res;
}
}
}
}
vector<long double> dp(1 << g, 1e15);
dp[0] = 0;
for (int mask = 0; mask < (1 << g); mask++) {
for (int j = 0; j < g; j++) {
if (!((1 << j) & mask)) {
long double cur = calc(groups[j].size());
long double temp = 0;
for (int i = 0; i < g; i++) {
if ((1 << i) & mask) {
temp += fromright[j][i][groups[j][0]];
}
}
long double temp1 = 0;
for (int i = 0; i < g; i++) {
if ((1 << i ) & mask) {
temp += fromleft[j][i][groups.back()];
}
}
cur += min(temp, temp1);
int l = 0, r = groups[j].size() - 1;
while (r - l > 2) {
int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
long double val1 = getans(mask, j, m1), val2 = getans(mask, j, m2);
if (val1 < val2) {
r = m2;
} else {
l = m1;
}
}
cur = min({cur, getans(mask, j, l), getans(mask, j, l+1), getans(mask, j, l+2)});
dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + cur);
}
}
}
cout << setprecision(30) << fixed << dp[(1 << g) - 1];
}
Compilation message
passes.cpp: In function 'long double getans(int, int, int)':
passes.cpp:45:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | if (k >= groups[j].size()) return 1e15;
| ~~^~~~~~~~~~~~~~~~~~~
passes.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | if (k + 1 == groups[j].size()) continue;
| ~~~~~~^~~~~~~~~~~~~~~~~~~
passes.cpp: In function 'int main()':
passes.cpp:138:47: error: no match for 'operator[]' (operand types are 'long double [100005]' and '__gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type' {aka 'std::vector<int>'})
138 | temp += fromleft[j][i][groups.back()];
| ^
