CODE FESTIVAL 2017 qual C: D - Yet Another Palindrome Partitioning

,

https://beta.atcoder.jp/contests/code-festival-2017-qualc/tasks/code_festival_2017_qualc_d

本番も解いたはずなのに見返してしばらく悩んでしまった。 本番では解くの遅くて順位低すぎて精神へのダメージがとても大きかった記憶がある。

solution

入力例$4$からも分かるように貪欲は嘘。DP。累積和を上手く使って加速。文字種$L = 26$を使って$O(NL)$。

$i$文字目までを回文に分割するときの最小値を$\mathrm{dp}(i)$とする。 区間$[l, r)$中に奇数回出現する文字種の集合を$f(l, r) \subseteq L$とすると、愚直な遷移は$\mathrm{dp}( r) = \min \{ \mathrm{dp}(l) + 1 \mid l \lt r, |f(l, r)| \le 1 \}$。 $O(N^2)$は間に合わないので加速したい。 $f(l, r)$を累積和$a_r$としてbitで表現し$f(0, r) \cong a_r \lt 2^L$とすれば、$l$として見るべきは$a_l = a_r \oplus c$ (ただし$\mathrm{popcount}( c) \le 1$)な$l$だけで十分。 長さ$2^L$の表を適当に作ってこれに対するDPのように直せば$O(NL)$となる。

implementation

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
using ll = long long;
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }

constexpr int inf = 1e9+7;
int main() {
    string s; cin >> s;
    int n = s.length();
    vector<int> acc(n + 1);
    repeat (i, n) {
        acc[i + 1] = acc[i] ^ (1 << (s[i] - 'a'));
    }
    unordered_map<int, vector<int> > f;
    vector<int> dp(n + 1, inf);
    dp[0] = 0;
    repeat (r, n) {
        f[acc[r]].push_back(r);
        repeat (c, 27) {
            int k = acc[r + 1] ^ (c == 26 ? 0 : (1 << c));
            if (f.count(k)) {
                auto & ls = f[k];
                repeat (i, min<int>(ls.size(), 300)) {
                    int l = ls[i];
                    setmin(dp[r + 1], dp[l] + 1);
                }
                if (ls.size() > 300) {
                    repeat_from (i, ls.size() - 300, ls.size()) {
                        int l = ls[i];
                        setmin(dp[r + 1], dp[l] + 1);
                    }
                }
            }
        }
    }
    cout << dp[n] << endl;
    return 0;
}