ABC110: C - String Transformation

見当違いの解法で解けなかった．1 対 1 の関係が作れるかどうかという問題．

問題

• ABC110: C - String Transformation

思考過程

WA だった実装は，

• S = "kd", T = "dd"
• S = "dd", T = "kd"

のように，同時に変えることのできないパターンがあれば No を出力するというものだった．

一応載せておく．

▶︎ソースコード展開

// ABC110_C
#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;
using ll = long long;

#define REP(i, n) for (ll i=0; i < n; i++)  // 0 ~ n-1

int main() {
    // input
    string S, T;
    cin >> S >> T;

    // calculation
    if (S == T) {
        cout << "Yes" << "\n";
    } else {
        set<char> alpha;
        REP(i, S.length()) {
            if (S[i] == T[i]) alpha.insert(S[i]);
        }

        char ch;
        bool flag = true;
        auto begin = alpha.begin(), end = alpha.end();
        for (auto itr = begin; itr != end; itr++) {
            ch = *itr;
            for (ll i = 0; i < S.length(); ++i) {
                if (T[i] == ch && S[i] != ch) {
                    flag = false;
                    break;
                }

                if (S[i] == ch && T[i] != ch) {
                    flag = false;
                    break;
                }
            }
            if (!flag) break;
        }

        if (flag) {
            cout << "Yes" << "\n";
        } else {
            cout << "No" << "\n";
        }
    }

    return 0;
}

解説

• editorial

www.youtube.com

「1 対 1 の文字対応表を作れるか」というのが解答であった（解説放送がめちゃめちゃ分かりやすかったのでおすすめ）．

（図が上手くかけなかった...）

ちょっと数学っぽくいうとアルファベットから別のアルファベットへの対応づけが「互いに単射」ならば Yes となります（別のものは別のものへ対応する．ただ，単射を実装することはできなかった...）．簡単な例を示しておきます．

# Yes の例
S = abc
T = aaa

# No の例
S = aaa
T = abc

私の解法だと，文字が異なるもの同士の対応を無視する形になっており，T[i] == S[i] のときのアルファベットについてしか考えられていないため WAになっている．

あとは上記の考えを実装する．解説に納得したが，実際「文字の対応を作る」という実装が自分には難しかった．以下の図のように，ペアを表す配列を作ると上手く対応関係を表現することができる．

実装例は以下．

// ABC110_C
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>  // std::copy()
using namespace std;
using ll = long long;

int main() {
    // input
    string S, T;
    cin >> S >> T;

    // calculation
    if (S == T) {
        cout << "Yes" << "\n";
    } else {
        // 対応関係を作る
        vector<ll> start(26, -1), goal(26, -1);
        ll sta, go;
        bool flag = true;
        for (ll i = 0; i < S.length(); ++i) {
            sta = S[i] - 'a';
            go = T[i] - 'a';
            if (start[sta] != -1 || goal[go] != -1) {
                // 既に書かれていた場合
                if (start[sta] != go || goal[go] != sta) {
                    // 対応関係が異なっていたら No
                    cout << "No" << "\n";
                    return 0;
                }
            } else {
                start[sta] = go;
                goal[go] = sta;
            }
        }
        cout << "Yes" << "\n";
    }
    return 0;
}

補足：アルファベット，数字を「数値」に変換する

アルファベットを数値に変換するには，'a' を引けば良い．数字を数値に変換するには '0' を引けば良い．

#include <iostream>
#include <vector>
#include <string>
using namespace std;
using ll = long long;

int main() {
    // input
    cout << 'a' - 'a' << "\n";
    cout << 'c' - 'a' << "\n";
    cout << 'g' - 'a' << "\n";
    cout << 'z' - 'a' << "\n";
    cout << '1' - '0' << "\n";
    cout << '3' - '0' << "\n";
    return 0;
}

出力

0
2
6
25
1
3