TopCoder SRM 727 Div2 Hard: ManageSubsequences

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

文字列 が与えられる。 に対して、部分列として を含むが は含まないように、いくつか文字を挿入したい。この条件を満たす文字挿入個数の最小値を求めよ。不可能な場合は を出力せよ。

解説

いったん のことは無視して、 に文字をいくつか追加して を部分列として含むにはどうすればよいかを考えることにしましょう。これは要するに LCS とほぼ同じで、「 の 文字目までを使って の 文字目までを含むようにするために必要な文字挿入個数の最小」を解けば良いことになります。状態遷移としては、 の次の文字を普通に入れるか、 の 文字目に相当する文字を挿入する パターンがありますので、次のような DP になります。

const int INF = 1 << 25;
int dp[310][310];
int main() {
    string S, A; cin >> S >> A;
    int len_s = S.length(), len_a = A.length();
    for(int i=0; i<=len_s; i++) {
        fill(dp[i], dp[i]+len_a+1, INF);
    }
    dp[0][0] = 0;
    for(int i=0; i<=len_s; i++) {
        for(int j=0; j<=len_a; j++) {
            // insert S[i]
            if(i < len_s) {
                int nxt_s = i+1;
                int nxt_a = j + (j < len_a && S[i] == A[j]);
                dp[nxt_s][nxt_a] = min(dp[nxt_s][nxt_a], dp[i][j]);
            }

            // insert A[j]
            if(j < len_a) {
                int nxt_s = i + (i < len_s && A[j] == S[i]);
                int nxt_a = j+1;
                dp[nxt_s][nxt_a] = min(dp[nxt_s][nxt_a], dp[i][j] + 1);
            }
        }
    }
    cout << dp[len_s][len_a] << endl;
    return 0;
}

ここに が増えても同様で、要するに が最後まで一致する前に と について最後まで一致すれば良いということになります。よって、 の DP で解くことができます。

ソースコード

int dp[2][310][310];
class ManageSubsequences {
    public:
    int minAdded(string S, string A, string B) {
        int len_s = S.length();
        int len_a = A.length();
        int len_b = B.length();

        for(int i=0; i<2; i++) {
            for(int j=0; j<=len_a; j++) {
                for(int k=0; k<=len_b; k++) {
                    dp[i][j][k] = INF;
                }
            }
        }
        dp[0][0][0] = 0;

        for(int i=0; i<=len_s; i++) {
            int cur = i % 2, nxt = cur ^ 1;
            for(int j=0; j<=len_a; j++) {
                for(int k=0; k<len_b; k++) {
                    // insert S[i]
                    if(i < len_s) {
                        int nxt_a = j + (j < len_a && S[i] == A[j]);
                        int nxt_b = k + (k < len_b && S[i] == B[k]);
                        chmin(dp[nxt][nxt_a][nxt_b], dp[cur][j][k]);
                    }

                    // insert A[j]
                    if(j < len_a) {
                        int nxt_mo = (cur + (i < len_s && A[j] == S[i])) % 2;
                        int nxt_b  = k + (k < len_b && A[j] == B[k]);
                        chmin(dp[nxt_mo][j+1][nxt_b], dp[cur][j][k] + 1);
                    }

                    if(i != len_s) dp[cur][j][k] = INF;
                }
            }
        }

        int ans = INF;
        for(int k=0; k<len_b; k++) chmin(ans, dp[len_s%2][len_a][k]);
        return (ans == INF ? -1 : ans);
    }
};