回文部分列 (Palindromic Subsequences) [Aizu Competitive Programming Camp 2018 Day 3 G]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day3/problems/G

前提知識

• 区間DP
• greedyからの帰着

考察過程

1. 似たような問題設定を見たことあった
2. DEGwerさんのgreedyからの帰着で解ける
3. それで区間DPすればいけそう

解法

https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC2018Day3/3149963

区間DPをする。
dp[L][R] := [0,L]と[R,N+1]の文字列で回分を貪欲に作ったときの組み合わせ数
ここで貪欲というのが重要。
元々作ってある回分にaaを足したい場合、Lから右にあるaのうちどれか、Rから左にあるaのうちどれか
のように自由度を高めてしまうと、重複して数える可能性が出てくる。
なので、貪欲に一番近いaを取るという風にしてしまうと、重複せず数え上げることができる。
　
なぜ重複しないのかというのが、DEGwerさんのgreedyからの帰着の話になるのだが、
ある回分があって、その回文が文字列の部分文字列として含まれるかの判定問題を考える。
その判定問題は左右から貪欲に文字を決定していけば含まれるかが分かるので、その挙動を遷移として採用するというもの。
　
遷移を書くときは事前に
go_migi[i][c] := i番目の文字から右に行って一番近い文字cがある添字
go_hidari[i][c] := i番目の文字から左に行って一番近い文字cがある添字
を累積和のような要領で作って、DPをしていく。
　
答えを数え上げるときは、遷移の最中に集計する。
if(len != N + 2) ans += dp[L][R];
これは偶数長の回分を集計している。（len=N+2のときはからの部分文字列なので排除）
if (LL <= RR) ans += dp[L][R];
これは奇数長の回分を集計している。
LL≦RRを満たすのならば(L,R)の間に該当する文字が1つはあるということなので、集計する。

string S; int N;
mint dp[2020][2020];
int go_migi[2020][26], go_hidari[2020][26];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    N = S.length();
    S = "#" + S + "#";

    rep(c, 0, 26) go_migi[N][c] = N + 1;
    rrep(i, N - 1, 0) {
        rep(c, 0, 26) go_migi[i][c] = go_migi[i + 1][c];
        go_migi[i][S[i + 1] - 'a'] = i + 1;
    }

    rep(c, 0, 26) go_hidari[1][c] = 0;
    rep(i, 2, N + 2) {
        rep(c, 0, 26) go_hidari[i][c] = go_hidari[i - 1][c];
        go_hidari[i][S[i - 1] - 'a'] = i - 1;
    }

    mint ans = 0;
    dp[0][N + 1] = 1;
    rrep(len, N + 2, 2) {
        rep(L, 0, N + 1) {
            int R = L + len - 1;
            if (N + 1 < R) break;

            if(len != N + 2) ans += dp[L][R];
            rep(c, 0, 26) {
                int LL = go_migi[L][c];
                int RR = go_hidari[R][c];

                if (LL <= RR) ans += dp[L][R];
                if (LL < RR) dp[LL][RR] += dp[L][R];
            }
        }
    }

    cout << ans << endl;
}