AtCoder Regular Contest 053 B : 回文分割

arc053.contest.atcoder.jp

解法

回文になるには、

  • 偶数個のみで構成される文
  • 偶数個と、1つの1文字で構成される文

であることが分かる。

なので、まず文字ごとの出現回数をカウントし、
奇数を1と残った偶数に分解してあげる。
すると、1の個数と偶数の合計になる。

この、いくつかある「1」に偶数から分配して
回文を作ると考える。

特殊化して、1の個数が0のときは、
偶数の合計を出力する。

それ以外のときは、その偶数を
1に2ずつ分配してあげる。

1に分配される数の最小値 = ((偶数の和 / 1の個数) / 2) * 2

で表せるので、これに1を足して出力。

Submission #937731 - AtCoder Regular Contest 053 | AtCoder