Codeforces Round 764 (Div. 3) D – Palindromes ColoringPalindromes Coloring を解いた記録
問題の概要
\(n\)個の英小文字を\(k\)個のグループに分ける．このとき，グループに属さない英小文字があってもよいが，どのグループにも1個以上の英小文字を割り当てなければならない．
各グループの中では回文になるように英小文字を並べなければならない．\(k\)個の回文のうち最短のものの長さを最大化し，その長さを答えよ．
制約
- \(1 \leq k \leq n \leq 2 \times 10^{5}\)
解法
同じ英小文字のペアが\(p\)個あれば，\(k\)個ある回文の長さは\(\lfloor p/k \rfloor \times 2\)以上にできます．
英小文字のペアのうち使われなかったものと英小文字のうちペアになれなかったものが合計\(k\)個あれば，それを回文の真ん中に挿入することで回文を1だけ伸ばせます．