Code Festival 2017 予選C D - Yet Another Palindrome Partitioning

面白い問題！

問題

英小文字のみからなる文字列sが与えられる
これをいくつかの空でない部分文字列s[1], s[2], ..., s[n]へ分割したい
更に任意のs[i]について、「s[i]の文字列を並び替えて回文が得られる」という条件も満たしたい
条件が成り立つようにsを分割するとき、分割数nの最小値を求めよ

1 <= |s| <= 2*10^5

解法

まず各文字を2進数表記にしたものの配列を考える
(具体的には文字cは1<<(c-'a')にする)
更にこれのxorでの累積和をとる
そうすることで出来る配列xのi番目は、「s[0,i]における各アルファベットの登場回数の偶奇(2で割った余り)」という状態を表す
つまりこれで立っているビットが1個以下ならその範囲は回文にできることになる
これを利用すればs[l,r]が回文にできるかはO(1)で求めることができる

これを利用したdpとしては
dp[i]: i文字目までの答え
dp[i] = min({dp[j] | s[j+1,i]が回文にできる}) + 1
というものがぱっと思いつく
けどこれだとO(|s|^2)になるから無理

そこでもう一つdp配列を用意する
dp2[b]: 今i文字目を見ているとして、x[j]=bとなるようなj(＜i)のうちdp[j]が最小であるようなもののdp[j]の値 (存在しなければinf)
でx[i]のビットを1個(か0個)反転したもの全て(26個)をbとして試してmin(dp2[b]+1)でdp[i]を更新すれば、更新がO(1)で出来るようになる

int n, x, dp[200200], dp2[1<<26];
string s;

signed main() {
	cin >> s;
	n = s.size();
	reps(i,1,1<<26) dp2[i] = inf;
	rep(i,n) {
		x ^= 1<<(s[i]-'a');
		int t = dp2[x];
		rep(k,26) chmin(t, dp2[x^(1<<k)]);
		chmin(dp2[x], t+1);
		dp[i] = t+1;
	}
	cout << dp[n-1] << endl;
}