#include <bits/stdc++.h>
using namespace std;
#define int long long
map<char, int> m;
const int MAXN = 1e5 + 5, MAXG = 15;
vector<vector<int>> pos;
int G;
long double dp[1 << MAXG], PREF[MAXG][MAXG][MAXN], SUF[MAXN][MAXN][MAXG];
long double compute(int i, int cnt, int mask) {
long double ret = 0;
int rcnt = pos[i].size() - cnt;
ret += cnt * (cnt - 1) * 0.25;
ret += rcnt * (rcnt - 1) * 0.25;
for (int j = 0; j < G; ++j) {
if (mask & (1 << j)) ret += (cnt ? PREF[i][j][cnt - 1] : 0) + (rcnt ? SUF[i][j][rcnt - 1] : 0);
}
return ret;
}
signed main() {
string s;
cin >> s;
vector<int> v(s.length());
int cnt = 0;
for (int i = 0; i < s.length(); ++i) {
if (m.find(s[i]) != m.end()) v[i] = m[s[i]];
else v[i] = m[s[i]] = cnt++;
}
G = *max_element(begin(v), end(v)) + 1;
pos.resize(G);
int n = s.length();
for (int i = 0; i < n; ++i) pos[v[i]].push_back(i);
dp[0] = 0;
for (int i = 0; i < G; ++i) {
for (int j = 0; j < G; ++j) {
if (i == j) continue;
int ptr = 0, cant = 0;
for (int k = 0; k < pos[i].size(); ++k) {
while (ptr < pos[i][k]) cant += v[ptr++] == j;
PREF[i][j][k] = cant;
if (k) PREF[i][j][k] += PREF[i][j][k - 1];
}
ptr = n - 1, cant = 0;
for (int k = 0; k < pos[i].size(); ++k) {
int idx = pos[i].size() - k - 1;
while (ptr > pos[i][idx]) cant += v[ptr--] == j;
SUF[i][j][k] = cant;
if (k) SUF[i][j][k] += SUF[i][j][k - 1];
}
}
}
for (int mask = 1; mask < (1 << G); mask++) {
dp[mask] = 1e18;
for (int i = 0; i < G; i++) {
if (!(mask & (1 << i))) continue;
long double EV = compute(i, pos[i].size(), mask);
int l = 0, r = pos[i].size() - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (compute(i, mid, mask) <= compute(i, mid + 1, mask)) EV = min(EV, compute(i, mid, mask)), r = mid - 1;
else l = mid + 1;
}
dp[mask] = min(dp[mask], EV + dp[mask ^ (1 << i)]);
}
}
cout << fixed << setprecision(8) << dp[(1 << G) - 1];
}
Compilation message
passes.cpp: In function 'int main()':
passes.cpp:24:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for (int i = 0; i < s.length(); ++i) {
| ~~^~~~~~~~~~~~
passes.cpp:37:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int k = 0; k < pos[i].size(); ++k) {
| ~~^~~~~~~~~~~~~~~
passes.cpp:43:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int k = 0; k < pos[i].size(); ++k) {
| ~~^~~~~~~~~~~~~~~
/tmp/ccfvOGj8.o: in function `compute(long long, long long, long long)':
passes.cpp:(.text+0xa): relocation truncated to fit: R_X86_64_PC32 against symbol `pos' defined in .bss section in /tmp/ccfvOGj8.o
passes.cpp:(.text+0x3f): relocation truncated to fit: R_X86_64_PC32 against symbol `G' defined in .bss section in /tmp/ccfvOGj8.o
passes.cpp:(.text+0xa1): relocation truncated to fit: R_X86_64_PC32 against symbol `PREF' defined in .bss section in /tmp/ccfvOGj8.o
/tmp/ccfvOGj8.o: in function `main':
passes.cpp:(.text.startup+0x8): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
passes.cpp:(.text.startup+0xd6): relocation truncated to fit: R_X86_64_PC32 against symbol `m' defined in .bss section in /tmp/ccfvOGj8.o
passes.cpp:(.text.startup+0xf0): relocation truncated to fit: R_X86_64_PC32 against symbol `m' defined in .bss section in /tmp/ccfvOGj8.o
passes.cpp:(.text.startup+0x123): relocation truncated to fit: R_X86_64_PC32 against symbol `m' defined in .bss section in /tmp/ccfvOGj8.o
passes.cpp:(.text.startup+0x13e): relocation truncated to fit: R_X86_64_PC32 against symbol `m' defined in .bss section in /tmp/ccfvOGj8.o
passes.cpp:(.text.startup+0x167): relocation truncated to fit: R_X86_64_PC32 against symbol `m' defined in .bss section in /tmp/ccfvOGj8.o
passes.cpp:(.text.startup+0x17f): relocation truncated to fit: R_X86_64_PC32 against symbol `m' defined in .bss section in /tmp/ccfvOGj8.o
passes.cpp:(.text.startup+0x1e2): additional relocation overflows omitted from the output
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
