ABC-110 C - String Transformation 別解説 - 茶処・まっちゃら亭の一休みばしょ

またここに来ました。
今回は緑梅していた時に公式の解説や他の人のユーザー解説とは異なった(かな？)解答をしていたので、一応共有しておきます。

※この解説は筆者が個人的に書いてるので、読者のみなさんが求める厳密な証明などは書かれていません。ご了承ください。

公式の説明(ざっくり)

正直私も正確に理解できてません(おい)が、とりあえず次が成り立てばいいということだと思われます。

$i \neq j$ であるとき、 $S_i = S_j$ ならば $T_i = T_j$ である...① (異なる英小文字に置換するので合ってそう)

これは、例えば

abcb
afdf

などの入力の場合だと、

a は何も操作しないようにする(明らかに $S_1 = T_1$ であるため)
b は $2 , 4$ 文字目にあり、f も同じ位置 $2 , 4$ 文字目にある
c は d に置換するなどする

ことで、答えは Yes になります。しかし、

abcb
afdk

などの入力では、

c は d に置換するなどするが、( $S =$ abcb 、 $T =$ afck となる)
b を f に置換すると $S =$ afcf 、 $T =$ abck となる
その後 k を b に置換すると、 $S =$ afcf 、 $T =$ akcb となってしまう

したがって答えは No になります。こうして実験してみると、確かに①を満たすときに限り成り立つことがわかります。

この $i , j$ を全探索してしまうと $O ( |S|^2 )$ となり間に合わなくなるので、置換表をうまく利用して $O ( |S|)$ に落とす、といった方法が書かれています。

自分なりに考えた解法

この""置換表""が私にはあまりよくわかっていないので、そんなことをせずに、各文字列 $S , T$ について次の配列を作って判定することを考えました。

$S_{ i , j } :=$ 文字列 $i$ ( $i=1$ のとき $S$ を、 $i=2$ のとき $T$ を表す) における $j\ ( 1\le j\le 26 )$ 番目のアルファベットがある index の配列

というか、単に $S , T$ に対して位置するアルファベットの index を配列として保管すればよいと思います。これは C++ 言語では map (連想配列) を用いて容易に実装可能です。

そして、今調べている文字列に対する map に対して異なる文字列について①の条件を満たすか調べればよいです。詳しくは以下の実装例をご覧ください。

以下は解答例です(C++)。こちらはSubmissionです。

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++) //[0,n)
#define srep(i,a,b) for(int i = a; i < b; i++) //[a,b)
#define all(A) (A).begin(),(A).end()
#define rall(A) (A).rbegin(),(A).rend()
#define pmt(A) next_permutation(all(A))
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<ll,ll>;
using pq = priority_queue<ll,vector<ll>,greater<ll>>;
const ll inf = 8e18;
const int iinf = (int)1e9;
const int mod9 = 998244353;
const int mod1 = 1000000007;
struct Edge { int to; ll cost; int from; };
bool compe(const Edge &e,const Edge &e2){ return e.cost < e2.cost; }
using Graph = vector<vector<int>>;
using EGraph = vector<Edge>;
using SGraph = vector<set<ll>>;
template <typename T>
int siz(T& a){return (int)a.size();}

bool judge(const map<char,vector<int>> mp,string base){
    bool aok = 1;
    for(auto& [k,v] : mp){
        bool ok = 1;
        if(siz(v) != 1){
            rep(i,siz(v)) if(base[v[0]] != base[v[i]]) ok = 0;
        }
        aok &= ok;
    }
    return aok;
}

int main(void){
    string s,t; cin >> s >> t;
    map<char,vector<int>> mpt,mps;
    rep(i,siz(t)) mpt[t[i]].push_back(i);
    rep(i,siz(s)) mps[s[i]].push_back(i);

    cout << (judge(mps,t) && judge(mpt,s) ? "Yes" : "No");
}

※1 judge 関数内において rep(i,siz(v)).. とありますが、拡張for文で実装してもいいと思います。その判定元となる文字 base[v[0]] の処理が余計にコードを増やすかなと思ったため、こう書いています。

※2 judge はどちらの文字列に対しても判定する必要があります。そうしなければ、例えば

ajaa
bjbn

や

bjbn
ajaa

の少なくとも $1$ つ以上のケースなどで落ちると思われます。

Epilogue

文字列も好きなんですよね～
なんか、こう、自由性がありますよね入力ケースなどに！！！！！！