もし置換に関してDPをするなら， どれを選んだかという集合を持ちながら遷移するので， \(O(2^{N})\) がかかって無理． そこで，最適戦略を考える方針にする．
いきなりは難しいので，簡単に考えるとすれば，
- 数字を1だけで考える
- 置換は互換のみ，とくに隣り合わせのみだと楽．
2以上の数字 \(k\) は，1 が\(k\) 個連続していると思ってもスコアは同じ． 次に，(隣同士の)互換について考える． ブロックを互換をしたとき，どの程度得をするのかを考えるとよい．
ブロック \(i\) におけるスコアを \(a_{i}\)， ブロックにおける x の個数を \(x_{i}\) とおく． ブロック \(i,j\) を入れ替えたときに，どの程度スコアが変化するか． ブロック \(j,i\) の順に並んでいるとするとき，このブロック間のスコアは \(x_{j} * a_{i}\) となる． よって，\(j,i\) の並びがスコアが最適であるためには， \(x_{j} a_{i} \leq x_{i}a{j}\) が必要十分．これは両辺を割ることで \(i,j\) だけの式にしても良い．
実装
最適な並び方はソートして求まる． 並び方を固定すれば，スコア自体は求まる． スコアを求めるときは， ブロック内とブロック間に分けて求めると楽． いずれも累積和を使うと簡単に求まる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n;
cin >> n;
vll a(n);
vll x(n);
rep(i,n){
for(auto c: s[i]){
if(c != 'X') a[i] += c - '0';
else x[i]++;
}
}
vll ind(n); rep(i,n) ind[i] = i;
sort(all(ind), [&](int k, int l){
return a[k]*x[l] < a[l]*x[k]; // <= : RE
});
// calc score
ll ans = 0;
// ブロック内
rep(k,n){
ll i = ind[k];
ll t = 0;
for(auto c: s[i]){
if(c == 'X') t++;
else ans += (c-'0')*t;
}
}
// ブロック間
ll t = 0;
rep(k,n){
ll i = ind[k];
ans += t*a[i];
t += x[i];
}
cout << ans << endl;
return 0;
}
