けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning (黄色, 700 点)

AtCoder AtCoder700点 DP DP高速化 変化・遷移先が限られる 区間分割型シーケンシャルDP 回文 考察：パリティに着目する DP高速化:累積和 累積和 bitDP 黄色diff スライドbitDP Zero-Sum Ranges 数量が小さいことの活用：文字の種類数 区間 最小回数・最小個数を求める 区間分割の仕方を走査する問題 最適化問題

遷移先を絞れる系の DP

問題へのリンク

問題概要

長さ N の文字列 S が与えられる。これを以下の条件を満たすように最小個数の区間に分割したい。最小個数を求めよ。

  • どの区間についても、区間内の文字を適切に並び替えると回文になる

制約

  • 1 \le N \le 1 \times 10^{5}

考えたこと

まず「文字列 T を並び替えると回文にできる」条件について考えておく。これは簡単で

  • T に登場する各文字について出現頻度を考えたとき、奇数個であるような文字がたかだか 1 個である

という風になる。よって、 S を上手に区間分割して、各区間が上記の条件を満たすようにする問題といえる。最初、左からまたは右から Greedy にうまくできないかと考えていたけど、

  • abpqrstuba

みたいなケースがある。これは結局すべての文字をバラバラにするしかないケースであって、Greedy にできるとは思えない。ちょっと Greedy な方向性で迷走しまくってしまった。

とりあえず O(N2) な DP に

とりあえず O(N^{2}) な DP はすぐに出る。こういう風に区間を分割していくタイプの DP はおなじみだ。

  • dp[ i ] := 最初の i 文字について条件を満たすように区間分割する方法のうちの、区間の個数の最小値

とすれば

  • chmin(dp[ i ], dp[ j ] + 1)　(区間 [j, i) が条件を満たす場合のみ)

という感じの遷移で解くことができる。これで O(N^{2}) にはなる。この手の DP を高速化する手段は本当にめちゃくちゃたくさんある。今回は「遷移先が絞れる」というタイプの問題だった。

遷移先が 26 通りに限られる

具体的には、

  • 各文字 c に対して、区間 [j, i) 内の文字 c の個数が奇数で他がすべて偶数となるような j

についてのみ調べればよいということになる。ただし、そのような j は一般には複数通り考えられることに注意する。そこで、

  • memo[ bit ] := 今まで見てきた中での、各文字の頻度パリティベクトルが bit となるような場合についての最小値

といったものを用意することにする。

  • 区間 [0, i) の頻度パリティベクトルを par とすると、区間 [j, i) 内の文字 c が奇数個で他がすべて偶数個になるような場合についての区間 [0, j) のパリティ par2 は自動的に決まるので、
  • chmin(dp[ i ], memo[ par2 ] + 1) と更新すればよい
  • さらにその結果をもとに chmin(memo[ par ], dp[ i ]) と更新しておく
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int INF = 1<<29;
string S;

int rev(int bit, int i) {
    return bit ^ (1<<i);
}

long long solve() {
    int N = S.size();

    vector<int> dp(N+1, INF);
    vector<int> mval(1<<26, INF);
    dp[0] = 0;
    mval[0] = 0;
    int par = 0;
    for (int i = 1; i <= N; ++i) {
        par = rev(par, S[i-1] - 'a');
        chmin(dp[i], mval[par] + 1);
        for (int j = 0; j < 26; ++j) {
            par = rev(par, j);
            chmin(dp[i], mval[par] + 1);
            par = rev(par, j);
        }
        chmin(mval[par], dp[i]);
    }       
    return dp[N];
}

int main() {
    while (cin >> S) cout << solve() << endl;
}