SRM663 Div1 Easy ABBADiv1

2015/07/24 (Fri) SRM 文字列 DP

問題

問題文

A, B からなる2つの文字列 $initial, target$ が与えられる．$initial$ に対して次の2つの操作ができる :

  • 末尾に A を加える
  • 末尾に B を加えて左右反転する

$initial$ から始めて $target$ にできるだろうか？

方針

$target$ から $initial$ に戻せるか考える． $target$ は，

  • 先頭が A, 末尾が A のときは，直前は末尾の A を取り除いた文字列
  • 先頭が A, 末尾が B のときは，直前は $initial$ と等しい文字列
  • 先頭が B, 末尾が A のときは，直前は末尾の A を取り除いた文字列か，先頭の B を取り除いて反転した文字列
  • 先頭が B, 末尾が B のときは，直前は先頭の B を取り除いて反転した文字列

に定まる．

「$dp[l][r][rev] := rev$ が true なら反転した $target$，そうでないなら反転してない $target$ の部分文字列 $[l,r]$ からはじめて $initial$ は作れるか？」という DP テーブルをメモ化再帰で埋める．

ちなみに，こんなインデックスも場合分けも間違えやすい DP をするよりもよい貪欲法もあります． mayokoさんの記事を見てください．

実装

class ABBADiv1 {
public:
    string canObtain(string initial_, string target_) {
        initial = initial_, target = target_;
        memset(dp,-1,sizeof(dp));
        return rec(0,target.size()-1,false) ? "Possible" : "Impossible";
    }
    string initial, target;
    char dp[60][60][2];
    bool rec(int l, int r, bool rev){
        char & res = dp[l][r][rev];
        if(res != -1) return dp[l][r][rev];
        if(r+1-l < (int)initial.size()) return res = false;
        if(r+1-l == (int)initial.size()){
            string x = target.substr(l,r+1-l);
            if(rev) reverse(all(x));
            return res = x == initial;
        }
        if(!rev){
            if(false){
            } else if(target[l] == 'B' && target[r] == 'A'){
                res = rec(l,r-1,rev) || rec(l+1,r,!rev);
            } else if(target[l] == 'B' && target[r] == 'B'){
                res = rec(l+1,r,!rev);
            } else if(target[l] == 'A' && target[r] == 'A'){
                res = rec(l,r-1,rev);
            } else if(target[l] == 'A' && target[r] == 'B'){
                res = false;
            }
        } else {
            if(false){
            } else if(target[r] == 'B' && target[l] == 'A'){
                res = rec(l+1,r,rev) || rec(l,r-1,!rev);
            } else if(target[r] == 'B' && target[l] == 'B'){
                res = rec(l,r-1,!rev);
            } else if(target[r] == 'A' && target[l] == 'A'){
                res = rec(l+1,r,rev);
            } else if(target[r] == 'A' && target[l] == 'B'){
                res = false;
            }
        }
        return res;
    }
};