559B - Equivalent Strings

Problem - B - Codeforces
Problem - D - Codeforces

• 復習。TLE するかもなぁ。と思いつつも他に解法が思いつかず提出して、案の定 TLE した問題。SRM なら撃墜されてんだろうな。
• 各再帰での 4 通りの分岐を事前の正規化で回避する。できる人には自然に出てくるアイデアなんだろうけど自分には素直にすごいなぁと思った。

class Div1B {
public:
    // 愚直に a,b を比較していくと O(4^log(n)) とかになって TLE する
    // メモ化してもダメ
    void solve_TLE(void) {
            string A,B;
            cin>>A>>B;

            map<pair<string,string>, bool> memo;
            function<bool(const string &, const string &)> rec = [&](const string &a, const string &b) {
                auto key = make_pair(a,b);
                if (memo.count(key))
                    return memo[key];
                if (a.length()%2==1)
                    return (memo[key] = (a==b));
                auto sz = a.length();
                string a1 = a.substr(0,sz/2);
                string a2 = a.substr(sz/2,sz/2);
                string b1 = b.substr(0,sz/2);
                string b2 = b.substr(sz/2,sz/2);

                bool ok = false;
                if (rec(a1,b1) && rec(a2,b2))
                    ok = true;
                if (rec(a1,b2) && rec(a2,b1))
                    ok = true;
                return (memo[key] = ok);
            };
            if (rec(A,B))
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
    }
    // そこで A,B を正規化してから比較する
    // 分割後の文字列を辞書式順序最小になるように結合しなおす。
    // solve_TLE にて a1,a2,b1,b2 を入れ替えて試す部分を事前に辞書式順にしておくことに並べて
    // おくことで分岐を不要にする
    void solve_optim(void) {
            string A,B;
            cin>>A>>B;

            // O(n*log(n))
            function<string(const string &)> normalize = [&](const string &s) {
                if (s.length()%2==1)
                    return s;
                string s1 = s.substr(0, s.length()/2);
                string s2 = s.substr(s.length()/2);
                s1 = normalize(s1);
                s2 = normalize(s2);
                if (s2 < s1)
                    return s2+s1;
                return s1+s2;
            };
            if (normalize(A)==normalize(B))
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
    }
    void solve() {
            solve_optim();
    }
};