ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning

動的計画法(DP)

問題
 提出コード

解法

$[l,r]$ が回文になる条件は、a ~ zについて、 $[l,r]$ に含まれる個数が全て偶数になる、もしくはどれか1つのみが奇数になる、のどちらかです。
a $= 0$ , b $=1$ , ..., z $=25$ とします。
先頭の文字から $i$ 番目の文字までを見て、奇数個になる文字 $c$ について、 $\sum_{c} 2^{c}$ を計算したものを $b_{i}$ とします。
$[l,r]$ が回文になる条件は、 $b_{r}$ と $b_{l-1}$ の排他的論理和を取った際に立つ2進数のbitが1個以下になる、というものに言い換えられます。

$dp[i] = i$ 文字目までで、分割できる回文の個数の最小値

を考えると、
$dp[i] = min(dp[j]) + 1 (ただしp(b_{i} \oplus b_{j}) \leq 1)$
という遷移が成り立ちます。
ここで、 $p(x)$ は $x$ を2進表記した際に立つビットの個数とします。
これだけみると $O(|S|^{2})$ になりますが、それぞれの2進表記で一番小さい値となるものをメモしておけば、27通りについて確認するだけで問題ありません(2進表記は、 $b_{i}$ が累積xorを取っているだけなので最大 $|S| + 1$ 通りです)。
あとはこれを計算し、 $dp[|S|]$ を求めればおしまいです。

感想

とても面白かったです。