이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/// -- -- ---- --- -- --
/// 12.04.2023 Wed 20:35
/// -- -- ---- --- -- --
#include <bits/stdc++.h>
using namespace std;
void abandoned_precalc();
#define pll pair<long long, long long>
#define all(a) (a).begin(), (a).end()
#define len(a) ((long long)(a).size())
#define add push_back
#define mkp make_pair
#define ll long long
#define fr first
#define sc second
const long long INF = 1000000000ll * 1000000003ll;
const long long MOD = 1000000007ll;
const int N = 2e5 + 5, G = 10;
string s;
ll ans4 = INF;
ll dp[(1 << G)];
ll asc[N], pref[N], suf[N];
ll cnt[N], sc;
int o(char x){ return x - 'A'; }
void solve(){
cin >> s;
// for(ll i = 0; i <= len(s); i++){
// ans4 = min(ans4, i * (i - 1) + (len(s) - i) * (len(s) - i - 1));
// }
// cout << (double)ans4 / 4. << "\n";
for(int i = 0; i < len(s); i++) asc[o(s[i])]++;
// for(int i = 0; i <= G; i++) cout << asc[i] << " ";
// cout << "\n";
for(int mask = 1; mask < (1 << G); mask++){
dp[mask] = INF;
fill(cnt, cnt + G, 0); sc = 0;
for(int i = len(s) - 1; ~i; i--){
if(!(mask & (1 << o(s[i])))) continue;
sc++; cnt[o(s[i])]++;
suf[o(s[i])] += sc - cnt[o(s[i])];
pref[o(s[i])] = 0;
}
for(int i = 0; i < G; i++){
if(!(mask & (1 << i))) continue;
dp[mask] = min(dp[mask], dp[mask ^ (1 << i)]
+ suf[i] * 4
+ cnt[i] * (cnt[i] - 1));
}
for(int i = 0, pc = 0; i < len(s); i++){
if(!(mask & (1 << o(s[i])))) continue;
suf[o(s[i])] -= sc - cnt[o(s[i])];
sc--; cnt[o(s[i])]--; pc++;
pref[o(s[i])] += pc - asc[o(s[i])] + cnt[o(s[i])];
dp[mask] = min(dp[mask], dp[mask ^ (1 << o(s[i]))]
+ (pref[o(s[i])] + suf[o(s[i])]) * 4
+ cnt[o(s[i])] * (cnt[o(s[i])] - 1) + (asc[o(s[i])] - cnt[o(s[i])]) * (asc[o(s[i])] - cnt[o(s[i])] - 1));
}
}
cout << (double)dp[(1 << G) - 1] / 4. << "\n";
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int _ = 1;
cout << fixed;
cout.precision(9);
abandoned_precalc();
// cin >> _ ;
while(_--) solve();
return 0;
}
/// ---- - -------- ------ -------- -- - - -
/// just a reminder. ubuntu password is i o i
/// ---- - -------- ------ -------- -- - - -
void abandoned_precalc(){
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |