Yet Another Palindrome Partitioning [CODE FESTIVAL 2017 予選C D]

http://code-festival-2017-qualc.contest.atcoder.jp/tasks/code_festival_2017_qualc_d

解説

http://code-festival-2017-qualc.contest.atcoder.jp/submissions/1706173

ある文字列が並び替えて回文となるのは「全ての文字が偶数個ある、または、奇数個の文字が1つだけある」場合である。
この典型を知っていないと今回の問題を解くのは難しい。
　
DPで解く。
まず、DPを考えてみると「dp[x] := x番目まででまとまりを作った時の分割数の最小」が思いつく。
以下、並び替えて回文となる部分列はvalidであると言うことにする。
この更新は
dp[x] = min{y＜xかつ[y,x)がvalid}(dp[y] + 1)
で行える。
　
これを愚直にやろうとすると、ある部分列がvalidであるかを高速に判定する必要がある。
ある部分列についてvalidであるかは、文字列のハッシュを使うことで高速に判定できる。
「x := iビット目が1であるならi番目の文字が奇数個ある」というハッシュを用意する(26ビットのハッシュ,longlong型で対応)。
すると、[x,y)のハッシュは[0,x]^[0,y]で計算できる。
あとは、そのハッシュについて1が立っている個数をpop_count等で取ればO(1)でできる。
　
これをやってもO(N^2)で間に合わないのだが、「[x,y)のハッシュは[0,x]^[0,y]で計算できる」というのを利用して高速化できる。
dp[x]を更新するのに確認するべきハッシュはそんなに多くはない。
[0,x]のハッシュに対して、
　[0,x] ^ ??? = 00000000000000000000000000
　[0,x] ^ ??? = 10000000000000000000000000
　[0,x] ^ ??? = 01000000000000000000000000
　…
　[0,x] ^ ??? = 00000000000000000000000001
の場合だけを考えればいいので、逆に言えば、ハッシュが
　??? = [0,x] ^ 00000000000000000000000000
　??? = [0,x] ^ 10000000000000000000000000
　??? = [0,x] ^ 01000000000000000000000000
　…
　??? = [0,x] ^ 00000000000000000000000001
となるx以前のdp[y]を見ていけばいい。
そのため、次のようなdp2を考える。
dp2[x] := [0,y]のハッシュがxとなる分割数の最小
こうすれば、dp[x]の更新には代わりに
　dp2[[0,x] ^ 00000000000000000000000000]
　dp2[[0,x] ^ 10000000000000000000000000]
　dp2[[0,x] ^ 01000000000000000000000000]
　…
　dp2[[0,x] ^ 00000000000000000000000001]
を見るだけでいい。最適化前はO(N)の遷移先だったのが、10個になったので、これで間に合う。

typedef long long ll;
#define INF INT_MAX/2
string S; int N;
int dp[201010];
unordered_map<ll, int> dp2;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S; N = S.length();
 
    ll x = 0;
    dp[0] = 0;
    dp2[0] = 0;
    int ans = 0;
    rep(i, 0, N) {
        x ^= 1LL << (S[i] - 'a');
        
        int ma = INF;
        if (!dp2.count(x)) dp2[x] = INF;
        ma = min(ma, dp2[x]);
 
        rep(i, 0, 26) {
            ll xx = x ^ (1LL << i);
            if (!dp2.count(xx)) dp2[xx] = INF;
            ma = min(ma, dp2[xx]);
        }
 
        dp2[x] = min(dp2[x], ma + 1);
        dp[i] = ma + 1;
    }
 
    cout << dp[N - 1] << endl;
}