// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (ll i = (a); i < (b); ++i)
#define per(i, a, b) for (ll i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)x.size()
#define pb push_back
#define mp make_pair
#define debug(x) cout<<#x<<" = "<<x<<endl
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
const ll INF = 1'000'000'007;
// 2^g state DP, what groups have boarded
// g transitions, next group to board
// to find optimal boarding side for next group we do not need to to O(N) thing
// instead we go through each group and find how many are to the left when doing binary search
// we precompute tables for each group
// something like O(2^g * g² * log n)
const ll g=15;
ll n;
string s;
double memo[1<<g];
vll groups_sum[g];
vll groups_pos[g];
vll groups_cross[g][g];
double dp(ll mask) {
if(mask==(1<<g)-1) return 0;
double &ans=memo[mask];
if(ans!=-1) return ans;
ans=1e10;
rep(i,0,g) if(!(mask&(1<<i))) {
ll group_size=sz(groups_pos[i]);
ll lo=0,hi=group_size;
while(lo!=hi) {
ll mid=(lo+hi)/2;
//cout<<"i = "<<i<<" mid = "<<mid<<endl;
ll pos=groups_pos[i][mid];
ll peopleL=0,peopleR=0;
rep(j,0,g) if(mask&(1<<j)) {
ll val=groups_sum[j][pos];
peopleL+=val;
peopleR+=group_size-val;
}
if(double(peopleL)+double(mid)/2.0<double(peopleR)+double(group_size-mid-1)/2.0) lo=mid+1;
else hi=mid;
}
rep(k,max(0LL,lo-1),min(group_size+1,lo+2)) {
double add=0;
rep(j,0,g) if(mask&(1<<j)) add+=double(groups_cross[i][j][k]);
ll peopleL=k,peopleR=(group_size)-peopleL;
add+=double(peopleL*(peopleL-1))/4.0+double(peopleR*(peopleR-1))/4.0;
//if(add==100800) cout<<"peopleL = "<<peopleL<<" peopleR = "<<peopleR<<endl;
ans=min(ans,dp(mask|(1<<i))+add);
}
}
//cout<<"mask = "<<mask<<" ans = "<<ans<<endl;
return ans;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
rep(i,0,1<<g) memo[i]=-1;
cin>>s;
n=sz(s);
trav(chr,s) chr-='A';
rep(i,0,g) groups_sum[i].assign(n+1,0);
rep(i,0,n) {
++groups_sum[(ll)s[i]][i];
groups_pos[(ll)s[i]].pb(i);
}
rep(i,0,g) rep(j,1,n) groups_sum[i][j]+=groups_sum[i][j-1];
rep(i,0,g) rep(j,0,g) {
ll val=0;
groups_cross[i][j].pb(0);
trav(pos,groups_pos[i]) {
val+=groups_sum[j][pos];
groups_cross[i][j].pb(val);
}
val=0;
per(k,0,sz(groups_pos[i])) {
ll pos=groups_pos[i][k];
val+=sz(groups_pos[j])-groups_sum[j][pos];
groups_cross[i][j][k]+=val;
}
}
cout<<setprecision(20)<<dp(0)<<endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
724 KB |
found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 |
Correct |
14 ms |
468 KB |
found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
3 |
Correct |
13 ms |
468 KB |
found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
4 |
Correct |
13 ms |
592 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 |
Correct |
16 ms |
840 KB |
found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 |
Correct |
41 ms |
20720 KB |
found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 |
Correct |
48 ms |
24472 KB |
found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 |
Correct |
49 ms |
25876 KB |
found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 |
Correct |
47 ms |
25904 KB |
found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
468 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 |
Correct |
14 ms |
596 KB |
found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 |
Incorrect |
30 ms |
620 KB |
1st numbers differ - expected: '1023.0000000000', found: '1029.5000000000', error = '0.0063538612' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
468 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 |
Correct |
14 ms |
596 KB |
found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 |
Incorrect |
30 ms |
620 KB |
1st numbers differ - expected: '1023.0000000000', found: '1029.5000000000', error = '0.0063538612' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
724 KB |
found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 |
Correct |
14 ms |
468 KB |
found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
3 |
Correct |
13 ms |
468 KB |
found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
4 |
Correct |
13 ms |
592 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 |
Correct |
16 ms |
840 KB |
found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 |
Correct |
41 ms |
20720 KB |
found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 |
Correct |
48 ms |
24472 KB |
found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 |
Correct |
49 ms |
25876 KB |
found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 |
Correct |
47 ms |
25904 KB |
found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
10 |
Correct |
15 ms |
468 KB |
found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
11 |
Correct |
14 ms |
596 KB |
found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
12 |
Incorrect |
30 ms |
620 KB |
1st numbers differ - expected: '1023.0000000000', found: '1029.5000000000', error = '0.0063538612' |
13 |
Halted |
0 ms |
0 KB |
- |