TopCoder SRM 727 Div1 Easy: OnlySanta

するめうめ

tsutaj.hatenablog.com

問題概要

文字列 が与えられる。 にいくつか文字を挿入して、"SANTA" を部分列として含み、かつ "SATAN" を部分列として含まないような文字列を構成せよ。

解説

方針は同じ回の Div2 Hard (hogecoder での解説) と全く同じです。この問題では文字列を復元する必要があるので、文字列を DP table に入れてとけばよいです。

ソースコード

string dp[1010][7][7];
class OnlySanta {
    public:
    string solve(string S) {
        string A = "SANTA", B = "SATAN";
        string INIT(1010, 'z');
        int len_s = S.length(), len_a = 5, len_b = 5;
        for(int i=0; i<=len_s; i++) {
            for(int j=0; j<=len_a; j++) {
                for(int k=0; k<=len_b; k++) {
                    dp[i][j][k] = INIT;
                }
            }
        }

        string ret = INIT;
        dp[0][0][0] = "";
        for(int i=0; i<=len_s; i++) {
            for(int j=0; j<=len_a; j++) {
                for(int k=0; k<len_b; k++) {
                    if(i == len_s && j == len_a) {
                        chmin(ret, dp[i][j][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[i+1][nxt_a][nxt_b], dp[i][j][k] + S[i]);
                    }

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