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; }