ユニークビジョンプログラミングコンテスト2022 夏 (AtCoder Beginner Contest 268) F - Best Concatenation (500)
すごい雑に考えるとXができるだけ前に多く有る方が嬉しい
先にそれぞれの文字列をどのように並べても獲得できるスコアを文字列毎に求めて足しておく
文字列毎にXの個数と数の和を求める
$ i番目の文字列のXの数を$ X_i、数の和を$ S_iとする
$ i番目が$ j番目より先にある時の追加スコアは$ X_i S_j
逆の場合は$ X_j S_i
なので$ X_i S_j \gt X_j S_iとなるようにペアをソートし、追加されるスコアを計算できる