はまやんはまやんはまやん

hamayanhamayan's blog

String Transformation [AtCoder Beginner Contest 110 C]

https://beta.atcoder.jp/contests/abc110/tasks/abc110_c

最初に載せた自分の解法が嘘解法でした!(一応下に残してあります)

解法

https://beta.atcoder.jp/contests/abc110/submissions/3261715

操作を考えてみると、自由度が高そうな感じがある。
任意の文字を別の文字に変えることはできそう。
しかし、ある文字を文字列中に存在する他の文字に変換することだけできない(同じ文字に変換はできない)。
よって、変換関数がvalidであるかを判定する。
文字列を元に「f[i][j] := 文字iを文字jに変換するか」を作ろう。
後は、
「ある文字について複数の変換先があってはいけない」
「ある文字について複数の変換元があってはいけない」
というルールをチェックして判定する。

string S, T;
int f[26][26];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> T;
    int N = S.length();
 
    rep(i, 0, N) {
        int a = S[i] - 'a';
        int b = T[i] - 'a';
 
        f[a][b] = 1;
    }
 
    rep(i, 0, 26) {
        int cn = 0;
        rep(j, 0, 26) if (f[i][j]) cn++;
        if (2 <= cn) {
            printf("No\n");
            return;
        }
    }
    rep(j, 0, 26) {
        int cn = 0;
        rep(i, 0, 26) if (f[i][j]) cn++;
        if (2 <= cn) {
            printf("No\n");
            return;
        }
    }
 
    printf("Yes\n");
}

嘘解法

https://beta.atcoder.jp/contests/abc110/submissions/3256344

一応残しておくけど、嘘解法です。
abb
aba
で落ちます。
変換しても場所の違いについて対応できていない(正しい解法は途中まで同じ)。

操作を考えてみると、自由度が高そうな感じがある。
任意の文字を別の文字に変えることはできそう。
しかし、ある文字を文字列中に存在する他の文字に変換することだけできない。
よって、文字毎に数を集計して、その数が集合として等しいなら、一致させることができる。
集合として等しいかを確認したいときは、ソートした列を比較すればいい。
vectorは比較関数があるので、そのまま比較できる。
f(s) := 文字列sをハッシュ化する関数

string S, T;
//---------------------------------------------------------------------------------------------------
vector<int> f(string s) {
    map<char, int> m;
    fore(c, s) m[c]++;
    vector<int> res;
    fore(p, m) res.push_back(p.second);
    sort(all(res));
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> T;
 
    if (f(S) == f(T)) printf("Yes\n");
    else printf("No\n");
}