mayoko’s diary

プロコンとかいろいろ。

SRM 509 div1 med:PalindromizationDiv1

SRM509の練習会に参加しました。easyだけ通しただけです。確か練習会ではmedを通した人がいなかったんですがmedは本番も異様に正解率低かったですね。僕も20回ぐらい提出してやっとACしました()

今回のeasyは簡単すぎると思うので省略します。

解法

基本的には区間DPです。
dp[l][r] = (区間[l, r]を回文にするためにかかる最低コスト)
とします。回文にするためには端っこから攻めていけば良いです。具体的には,
・word[l]を消してさらに[l+1, r]で回文にする
・word[r]を消してさらに[l, r-1]で回文にする
・word[l]の左にword[r]と同じ文字を追加してさらに[l, r-1]で回文にする
・word[r]の右にword[l]と同じ文字を追加してさらに[l+1, r]で回文にする
・端っこを両方共同じ文字に変えてさらに[l+1, r-1]で回文にする
・word[l]の左を変更してword[r]の右にその文字を追加し,さらに[l+1, r]で回文にする
・word[r]の右を変更してword[l]の左にその文字を追加し,さらに[l, r-1]で回文にする

最後の3つになかなか気づきませんでした…(しかもサンプルは通るっていう…)

で,このアイデアと同時に,すこし注意すべきことがあって,例えば文字aからbに直接変更するのは100かかるけど文字cを経由するとa->cにコスト1でc->bにコスト2だからこっちで文字を変えるほうがお得みたいなことがあります。文字の追加,消去についても同様です。

これを最初にワーシャルフロイドで処理しましょう(これも結構難しいアイデアな気がする)。

int n;
const ll INF = 1e9;

ll add[30], erase[30], change[30][30];
string word;
ll dp[55][55];

int parse(string s) {
    int ret = 0;
    for (char c : s) {
        ret = ret*10 + (c-'0');
    }
    return ret;
}

// [l, r]
ll dfs(int l, int r) {
    if (l >= r) return 0;
    ll& ret = dp[l][r];
    if (ret != -1) return ret;
    ret = INF;
    int cl = word[l]-'a';
    int cr = word[r]-'a';
    // 消す
    ret = min(ret, erase[cl]+dfs(l+1, r));
    ret = min(ret, erase[cr]+dfs(l, r-1));
    // 追加する
    ret = min(ret, add[cl]+dfs(l+1, r));
    ret = min(ret, add[cr]+dfs(l, r-1));
    // 変える
    for (int i = 0; i < 30; i++) {
        ret = min(ret, change[cl][i]+change[cr][i]+dfs(l+1, r-1));
        ret = min(ret, change[cl][i]+add[i]+dfs(l+1, r));
        ret = min(ret, change[cr][i]+add[i]+dfs(l, r-1));
    }
    return ret;
}

class PalindromizationDiv1 {
public:
    int getMinimumCost(string Word, vector <string> operations) {
        // input
        word = Word;
        n = word.size();
        for (int i = 0; i < 30; i++) {
            add[i] = INF;
            erase[i] = INF;
        }
        for (int i = 0; i < 30; i++) {
            for (int j = 0; j < 30; j++) {
                change[i][j] = INF;
            }
            change[i][i] = 0;
        }
        memset(dp, -1, sizeof(dp));
        for (auto s : operations) {
            if (s.substr(0, 3) == "add") {
                add[s[4]-'a'] = parse(s.substr(6));
            } else if (s.substr(0, 5) == "erase") {
                erase[s[6]-'a'] = parse(s.substr(8));
            } else {
                change[s[7]-'a'][s[9]-'a'] = parse(s.substr(11));
            }
        }
        // warshall
        // change
        for (int k = 0; k < 30; k++) {
            for (int i = 0; i < 30; i++) {
                for (int j = 0; j < 30; j++) {
                    change[i][j] = min(change[i][j], change[i][k] + change[k][j]);
                }
            }
        }
        // add/erase
        for (int k = 0; k < 30; k++) {
            for (int i = 0; i < 30; i++) {
                for (int j = 0; j < 30; j++) {
                    add[i] = min(add[i], add[j]+change[j][i]);
                    erase[i] = min(erase[i], erase[j]+change[i][j]);
                }
            }
        }
        int ans = dfs(0, n-1);
        if (ans == INF) return -1;
        return ans;
    }
};