SRM 663 div1 easy:ABBADiv1 - mayoko’s diary

SRM663に参加しました。結果はeasyをそこそこ早解きでレートが上がりました。試験期間終わってからずっとレートが下がってたのでとりあえず一安心です。

問題

解法

targetからA,Bを取り除いてinitialを作ることを考えます。

要するに,Aが末尾にあれば末尾からAを取り除いた文字列,Bが先頭にあればそのBを取り除いて文字列を反転させた文字列を候補として追加していきながら,,initialと同じ文字列を候補として持つかを調べます。

候補の数が $O(2^n)$ になるのでは無いかと思われるかもしれませんが,2通りに分散するような文字列B.....Aというのは,候補がA......, B......の2通りに派生し,これはこれ以降複数通りに派生することは無いので,候補数は大して増えません(おそらくBAAAAAAAAAAAというのが最悪ケースですがこれでも候補数は各文字数につきたかだか $O(n)$ です)。

class ABBADiv1 {
public:
    string canObtain(string initial, string target) {
        vector<string> from;
        from.push_back(target);
        int n = target.size();
        int m = initial.size();
        for (int i = 0; i < n-m; i++) {
            vector<string> to;
            for (string s : from) {
                if (s.back() == 'A') to.push_back(s.substr(0, s.size()-1));
                if (s[0] == 'B') {
                    reverse(s.begin(), s.end());
                    to.push_back(s.substr(0, s.size()-1));
                }
            }
            from = to;
            for (string s : from) cout << s << endl;
            cout << endl;
        }
        for (string& s : from) if (initial == s) return "Possible";
        return "Impossible";
    }
};