CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning

AtCoder 回文 問題記録 CODE FESTIVAL

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

問題概要

英小文字のみからなる文字列Sをいくつかの箇所で区切り、空でない部分文字列に分割することを考える。このとき必ずすべての部分文字列が「並べ替えれば回文にできる」という条件を満たすように分割しなければならない。可能な分割の最小数を求めよ。

|S| <= 2×105

解法

（なんか無駄に複雑なことをしている気もするので他の人の解説も見てください）

ある文字列が「並べ替えれば回文にできる」とは「奇数回登場する文字が高々1つ」と同値である。これは直観的には両端から文字を埋めて回文を作っていくことを考えるとわかりやすい。もしすべての文字が偶数個であるなら同じ文字を2個ずつとって両端に詰めていけばよいし、ひとつだけ奇数個の文字があるならそのプロセスの最後に余った1個を真ん中に置けばよい。

以上より重要なのは各文字が現れた回数の偶奇であるとわかった。ここで各文字の偶奇に0/1を割り当てると、これを長さ26のビット列で表すことができる（一例としてaとzが奇数回登場していて他が偶数回の場合、これに対応するビット列は 10000000000000000000000001 のようになる）。この表現の元では、ある区間において「奇数回登場する文字が高々1つ」というのは「立っているビットが高々1つ」と言い換えることができる。

ここで上のようなビット列においてSの左端から累積xorを取った数列をAとする。ただしA[0]は空文字列として00000000000000000000000000を割り当てる。こうすると累積和と同じように (A[n] xor A[m-1]) でm文字目～n文字目までの各文字の偶奇を得ることができるようになる。つまり「Sの区間[i, j]が条件を満たす」ならば「(A[j] xor A[i-1]) の立っているビットが高々1つ」である。

準備が整ったので以下のようなDPを考える。

dp(n): 1～n文字目だけを考えて分割を行ったときの最小分割数

このdpを小さいnから更新していく。ここでdp(n)が確定したとき、「Sの区間[n+1, m]が条件を満たすようなすべてのm」について、dp(m)=dp(n)+1という更新をかけることができる（n文字目までがdp(n)個に分割できて、n+1文字目～m文字目が1個に分割できるため）。問題はmをどうやって得るかだが、ここで上の累積xorを使うとそのようなmは (A[m] xor A[n]) の立っているビットが高々1つ、つまりA[n]と同一かあるいはひとつだけビットを反転させたようなA[m]を持つようなmが条件を満たす。前計算でA[i]=bを逆引きしてbからiを列挙できるようにしておけば、mの取得は簡単である。以上でDPを最後まで更新していけばdp(|S|)が答えになる。

注意点として、上のようなDPの配り方を愚直にやると遷移の数が|S|^2になりうるのでそのままだとTLEする（たとえばaaaaaaaaaaaa...は全部が全部に遷移できる）。これを避けるためには、あるビット列に遷移しようとするとき、以前にもそのビット列に遷移していて、かつそのときのdp値が今より小さければその遷移はスキップするという枝刈りが必要。こうするとある特定のビット列への遷移は高々27回までしか行われないので、結局O(N)時間に収まる（たぶん）。

感想

「DPはDAGの最短経路」を地で行く考察ができた感があり、良かった

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
void main() {
    auto S = readln.chomp;
    auto N = S.length.to!int;
    auto X = new int[](N+1);
    int[][int] Y;
    X[0] = 0;
    Y[0] = [0];
    foreach (i; 0..N) {
        int c = S[i] - 'a';
        X[i+1] = X[i] ^ (1 << c);
        Y[X[i+1]] ~= i+1;
    }
 
 
    auto dp = new int[](N+1);
    dp.fill(1 << 29);
    dp[0] = 0;
    int[int] used;
 
    foreach (i; 0..N) {
        foreach (j; 0..26) {
            int next = X[i] ^ (1 << j);
            if (next in Y && (!(next in used) || used[next] > dp[i])) {
                used[next] = dp[i];
                foreach (m; Y[next]) {
                    dp[m] = min(dp[m], dp[i]+1);
                }
            }
        }
 
        if (X[i] in Y && (!(X[i] in used) || used[X[i]] > dp[i])) {
            used[X[i]] = dp[i];
            foreach (m; Y[X[i]]) {
                dp[m] = min(dp[m], dp[i]+1);
            }
        }
    }
 
    dp[N].writeln;
}