CODE FESTIVAL qual C - D Yet Another Palindrome Partitioning (700)

• 問題

問題概要

文字列Sが与えられる。
Sを各々が並び替えれば回文にできるような部分文字列に分割するときその最小数を求めよ。
1 <= |S| <= 2*10⁵

解法

回文条件を言い換えると、「文字列の中に奇数回出てくるようなアルファベットはたかだか1種類である」となる。
文字列sに対して以下を満たすようにh(s)を定める。

'a' の出現回数 % 2 -> h(s)の1ビット目
'b' の出現回数 % 2 -> h(s)の2ビット目
....
'z' の出現回数 % 2 -> h(s)の26ビット目
ここで、h(s) = (0 または 1<<k) (0<=k<26)であればsは回文条件を満たす。

Sに対して、a[i] = h(S[0,i))と定める。
すると、h(S[l,r)) = a[l] ^ a[r] である。

以下のようなDPが組める。以下0<=k<26とする。
opt(i) = min(S[0,i)の分割回数),opt(0)=0として、
opt(i) = min_(0<=j<=i かつ a[j]^a[i]=0 or 1<<k )(opt(j)+1)
ただこれはO(N²)なので間に合わない。

ここで,
a[j] ^ a[i] = 0 <-> a[i] = a[j]
a[j] ^ a[i] = (1 << k) <-> a[i] = a[j] ^ (1<<k)
cf. (a ^ b) ^ c = a ^ (b ^ c), a ^ a=0
であることに注目すれば,(すなわち同じか1bitしか変わらない)
h(s)を引数とすれば遷移式には26個のminを取れば良いことがわかる。

すなわちdp[x]=min(h(s[0,x))なるsの交換回数)として、
初期状態 dp[0] = 0,
遷移式 dp[x] = min(dp[x],dp[x ^ (1<<k)])
dp[a[N]]が答えとなる。
ただし、a[N]=0の時dp[a[N]]=1となるので、max(dp[a[N]],1)とする。

メモ

O(N²)っぽい解法は思いついたが書けなかった。 回文条件の言い換えは応用が多そうなので押さえておきたい。 それとxorをスマートに書けるように。 a[0]=a[1<<k]=1として初期化したら通らなかったのだがなぜだろう。

コード

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 200005;
const ll lmod = 1e9+7;

int dp[1<<26];
int a[MAX_N]; //[0,i)のハッシュ値
int C = 26;
string S;

int main(){
  cin >> S ;
  int N = S.size();
  rep(i,N){
    int b = S[i] - 'a';
    a[i+1] = a[i] ^ (1<<b);
  }
  fill(dp,dp+(1<<26),INF);
  dp[0] = 0;
  REP(i,1,N+1){
    rep(j,C){
      int bit = 1<<j;
      dp[a[i]] = min(dp[a[i]],dp[a[i]^bit]+1);
    }
  }
  cout << max(1,dp[a[N]]) << endl;
  return 0;
}