問題概要

長さ $n (\leq 2 \times 10^5) $ の文字列 $s, t $ がある． $s, t $ に対し，ある長さ $\mathit{len} $ を1つ決めて，以下の操作を任意回数繰り返す．

$s $ の長さ $\mathit{len} $ の部分文字列を選び，反転させる．同時に， $t $ の長さ $\mathit{len} $ の部分文字列を選び，反転させる．

この操作により $s, t $ を等しくすることができるかどうかを求めよ．

クエリは $q (\leq 10^4) $ 個与えられる．ただし，全てのクエリについての $n $ の和が $2 \times 10^5 $ を超えることはない．

解法概要

文字構成が $s $ と $t $ で異なる (出現回数が異なる文字がある) ときは明らかに NO．以下，文字構成が同じ場合のみを考える．

反転操作の回数に制限はないので， $\mathit{len} = 2 $ (つまり隣接要素同士の交換のみ) と考えてよい ( $\mathit{len} \geq 3 $ となる操作は $\mathit{len} = 2 $ での操作を組み合わせて実現できる) ．

また1回の操作で必ず $s, t $ 両方で部分文字列を反転する必要があることから， $s $ を $t $ (あるいはその逆) に等しくするために必要な隣接要素同士の交換の回数は偶数回でなければならない．この偶奇は交換の順序やどの2要素を交換するかにはよらない (cf. 置換と偶置換・奇置換に関する基礎的なこと | 高校数学の美しい物語) ので，'a' を最小， 'z' と最大と考えたときの $s $ と $t $ の転倒数を求め，その偶奇が一致するかどうかを見ればよい．

ただし $s $ か $t $ のいずれかに複数回登場する文字が存在する場合は注意．同じ文字同士の交換によって交換回数を稼ぐことができるので，この場合は転倒数の偶奇が一致しなくても YES である．

ソースコード

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <string>
    #include <functional>
     
    using namespace std;
     
    using ll =  long long;
     
    template<typename T>class BIT {
        public:
        size_t n;
        vector<T> bit;
        T def;
        function<T(T, T)> update_func;
        function<T(T, T)> find_func;
        
        BIT(size_t _n, T _def, function<T(T, T)> _update_func, function<T(T, T)> _find_func)
            : n(_n), def(_def), update_func(_update_func), find_func(_find_func) {
            bit.resize(_n+1);
            fill(bit.begin(), bit.end(), _def);
        }
     
        void update(int idx, T x){
            for(int i=idx;i<=n;i+=i&-i) bit[i] = update_func(bit[i], x);
        }
     
        //bit[1]からbit[end]までの演算結果 (閉区間)
        T find(int end){
            T ret = (T)def;
            for(int i=end;i>=1;i-=i&-i) ret = find_func(ret, bit[i]);
            return ret;
        }
    };
     
    int count_swap(string &s, int n) {
        BIT<int> tree(26, 0, [](int a, int b){ return a+b; }, [](int a, int b){ return a+b; });
        int swap_cnt = 0;
        tree.update(s[0]-'a'+1, 1);
        for(int i=1;i<n;++i) {
            swap_cnt += tree.find(s[i]-'a'+1-1);
            tree.update(s[i]-'a'+1, 1);
        }
        return swap_cnt;
    }
     
    void solve() {
        int n;
        cin >> n;
        string s, t;
        cin >> s;
        cin >> t;
     
        vector<int> s_cnt(26, 0), t_cnt(26, 0);
        for(int i=0;i<n;++i) {
            ++s_cnt[s[i]-'a'];
            ++t_cnt[t[i]-'a'];
        }
        // 同じ文字の交換で交換回数稼ぎができるか？
        bool has_same_char = (*max_element(s_cnt.begin(), s_cnt.end()) >= 2 || *max_element(t_cnt.begin(), t_cnt.end()) >= 2);
     
        int s_swap_cnt = count_swap(s, n);
        int t_swap_cnt = count_swap(t, n);
     
        if(s_cnt != t_cnt || (s_swap_cnt % 2 != t_swap_cnt % 2 && !has_same_char)) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
        }
    }
     
    int main() {
        int q;
        cin >> q;
        while(q--) {
            solve();
        }
     
    }

所感

Div. 3 は全完できるようになりたいよなあ．

NoiminのNoise

Codeforces Round #598 Div. 3 F. Equalizing Two Strings

問題概要

解法概要

ソースコード

所感