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

概要

英小文字のみからなる文字列が与えられる。

をいくつかの空でない部分文字列に分割する。

そのとき、部分文字列は以下の条件を満たす。
・の文字を並べ替えて回文が得られる。

文字列の最小の分割数を求めよ。

問題文
D: Yet Another Palindrome Partitioning - CODE FESTIVAL 2017 qual C | AtCoder

解法

まず、並べ替えたら回文になる文字列とは、出現回数が奇数回であるような文字の数が1以下の文字列のことである。

それぞれの文字の登場回数の偶奇は、26bitのビット列で管理できる。

dp[i] : ビット列がiのときの最小の分割数とする。
:= {j | 0 ≤ j < i かつ j xor i は 2 のべき乗または 0 である(回文の条件) } とすると，
dp[i] = { dp[j] } + 1 である。 j xor i が2 のべき乗または 0 であるようなjは、i xor (1 << k)(0 ≤ k < 26)で全て見れる。

これを文字列の最初から最後までbit列を変化させながら行い、dp[最終的なbit列]が答えになる。(これが0になる場合もあるが、その時の答えは1)

公式解説
https://img.atcoder.jp/code-festival-2017-qualc/editorial.pdf

ソースコード

int dp[1 << 26];

signed main() {
    string s;
    int n, bit = 0;

    cin >> s;
    n = s.size();

    fill_n(dp, 1 << 26, INF);
    dp[0] = 0;
    Rep(i, n) {
        bit ^= 1 << (s[i] - 'a');
        Rep(j, 26) {
            dp[bit] = min(dp[bit], dp[bit ^ (1 << j)] + 1);
        }
    }

    cout << max(1, dp[bit]) << endl;
    return 0;
}

反省とか

コンテスト中は、できるだけ長い回文を左から作っていくみたいに考えてしまった。
xorの特性みたいなものは知っておいた方がいいと思った。
int を long long でdefineしてるとTLEするので注意。