けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 110 C - String Transformation (300 点)

ごめんなさい!!!!!

コンテスト中に僕が AC した解法は嘘解法でした (てんぷらさんたちに教えてもらいました)!!!

コンテスト終了後の TL を見ていると、同じ嘘解法で AC している人がたくさんいた感じだった。

問題概要 (ABC 110 C)

文字列 S, T が与えられ、S を以下の操作を好きなだけ行って T にできるかどうかを判定せよ:

  • 2 つの英小文字 c1, c2 を好きなように選んで、S 中の c1 をすべて c2 に、c2 をすべて c1 に置き換える

制約

  • 1 <= |S| = |T| = 105

解法

自分がやったのは嘘でした。。。(個数のみカウント)
ダメなケースとして

aab cdd

これが Yes になってしまう (正しくは No)

ちゃんとした解法では、まずは

  • S 中の同じ文字が T の異なる文字に対応しない
  • T 中の同じ文字が S の異なる文字に対応しない

を満たしていないとダメなことはわかる。そしてこれを満たしていれば、必ず変換できることも示せる。厳密に証明しようと思ったら

  • いくつかの要素の並びに対する任意の並び替え操作は、「2 つの要素の swap」を繰り返すことで実現できる

ということから言える。c1 と c2 を入れ替える操作は、a〜z の並びに対する、c1 と c2 との swap と思うことができる。

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main() {
    string S, T;
    cin >> S >> T;
    bool ok = true;
    map<char,char> ma, ima;
    for (int i = 0; i < S.size(); ++i) {
        char s = S[i], t = T[i];
        if (ma.count(s)) if (ma[s] != t) ok = false;
        if (ima.count(t)) if (ima[t] != s) ok = false;
        ma[s] = t; ima[t] = s;
    }
    if (ok) puts("Yes");
    else puts("No");
}