ABC110C String Transformation

解くのにかかった時間 35分くらい

int main()
{
    cout <<setprecision(10);
 
    string S , T ;
    cin >> S >> T ;
    map<char,char> Trans;
    int n = S.size();
 
    rep(i,n){
        if(!Trans.count(S[i])){
            Trans[S[i]] = T[i];
        }else { // 既にそれを keyとするのが存在していて、値が変わるのはダメ
            char ever = Trans[S[i]];
            if(ever != T[i]){//移動先が違うものっていうのは
                cout << "No" << endl;
                return 0;
            }
        }
    }
 
    map<char,char> RevTrans;
 
    rep(i,n){
        if(!RevTrans.count(T[i])){
            RevTrans[T[i]] = S[i];
        }else { // 既にそれを keyとするのが存在していて、値が変わるのはダメ
            char ever = RevTrans[T[i]];
            if(ever != S[i]){//移動先が違うものっていうのは
                cout << "NO" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
}

解法

サンプルコードから学ぶ

サンプルコードには

chokudai （さん）を redcoder にはできないと書いてある

（いやまあ、chokudai さんは redcoder なのでこれは Yes を出力すべきではあるのだが…）

chokudai

redcoder

なぜできないのか考えてみよう

まず、一番左のc と一番右の i を r にしなきゃいけないから、

一番左を S[0,]一番右をS[n]として

最終的に S[0] = S[n]となった状態で S[0] , S[n]を rにするんだなって思いつく。

S[0] を S[n]にしてみよう

c を i にすればいいね。 c → i

ここで気づく。あれ？i → c になるじゃん。

あれ、ダメか。

じゃあ次

S[0のc を a にして、 a を iにしてから二つのiをrにしよう。

つまり

〇 → △ → ̻□ （〇がc 、△がa 、□がi)

□ → r

ここでまた気が付く。

あれ？これでもダメじゃん

ここでさらに気が付く

「この問題難しくね？？？？？？？？？」

そう。この問題は難しい

どうして出来ないのかをchokudai(さん)の例から考える。

とりあえず

chokudai

〇edcode〇みたいなとき同時に〇にするしかない

一枚画像を貼っておきます f:id:niboshi_bisyoujo:20191123013905j:plain

なるほどSの文字を左から見ていって、Tの文字と対応させていくのか。

連想配列を使おう（map) Trans;

Transは文字をキー、文字をvalueとするmap

基本的に Trans[S[i]] = T[i] とするんだが、どういうときにダメになってしまうのかを考える。

①

文字列 S = abc

文字列 T = bab

みたいなのがあったとき

Trans[a] = 'b'

Trans[b] = 'a'

Trans[c] ='b'

これはchokudai

を redcoderにするときにやったときと同じパターンで、できない

②

文字列 S = aba

文字列T = cba

みたいなのがあったとき、Transが作られる順番はまず Trans[a] = 'c'

Trans[b] = 'b' ;

で次 Trans[a] = 'a'をしようとしたとき、にダメになる

（説明しようと思うけどなんか難しいので頑張って、chokudai redcoderの逆みたいなノリ（俺もわからん））

上の二つを言葉でいうと

変更前（文字列の変更）の文字が違くて、移動後が同じなのはダメ

みたいな？

あとついでに

その逆もだめ

これを二つのmapでぐりぐりってやって、

変更前（つまりSの文字）が同じなのに変更後（つまりTの文字）が違うもの指定してるよ～～！！

もしくはその逆、ってなったら No を出力するみたいなコードを書けば解ける

なんかおまけ

解説pdfを読んで、SとTの文字が一対一の対応にできるか！みたいなのはあ～なるほどね。ってなります。

なります。きっと誰でも。俺もお前も

でも、その実装良く分かりません。きっと誰でも、俺も、お前も。

そんな人はAtCoderの動画見てください

解いた後に見ればめちゃくちゃ頭すっきりしますよ。僕のこの記事読むよりも百億倍マシ。