比較的普通の問題っぽい

問題概要

文字列 $S$ が与えられる。
$S$ に含まれる文字をそれぞれ一度ずつ使い、何個かの回文を作ることを考えます。文字は自由な順序で使用することができ、 $S$ に複数回現れる文字は合計でその回数だけ使用します。

長さ $L$ の回文を 1 個作るごとに、 $L^{2}$ のスコアが得られます。最大で合計いくつのスコアを得ることができるでしょうか？

制約

$1 \le |S| \le 10^{5}$

考えたこと

二乗が強いので、とにかく長いのを作ってしまいたい。

理論上最大長さの回文を作る
このとき余ったやつは、いずれも同じ種類の文字は 1 個だけという状態になる (もし同じ種類の文字が 2 個以上余ったらそれを回文に使えるため)

というわけで、'a'〜'z' がそれぞれ何個ずつになるかを数えて、理論上最大の回文を作れば良い。作り方は

各文字について
- 偶数なら全部使う
- 奇数なら 1 個余して全部使う
それを終えたときに、余ったやつがあったら 1 個だけ回文の真ん中に使う

という風にすればよい。

#include <iostream>
#include <string>
using namespace std;

int num[26];

int main() {
    string S;
    cin >> S;
    for (auto c : S) num[c - 'a']++;

    long long ml = 0;
    long long rem = 0;
    for (int i = 0; i < 26; ++i) {
        ml += num[i] / 2 * 2;
        rem += num[i] % 2;
    }

    // 余ったら
    if (rem) {
        ++ml;
        --rem;
    }
    cout << ml * ml + rem << endl;
}