ごめんなさい!!!!!
コンテスト中に僕が AC した解法は嘘解法でした (てんぷらさんたちに教えてもらいました)!!!
- 嘘解法 :https://beta.atcoder.jp/contests/abc110/submissions/3251109
- S と T の各文字の個数をカウントして、それぞれ個数ベクトルをソートして一致するか
- やり直し:https://beta.atcoder.jp/contests/abc110/submissions/3259263
- 「S 中の同じ文字が T の異なる文字に対応しない」かつ「T 中の同じ文字が S の異なる文字に対応しない」が必要十分条件
コンテスト終了後の TL を見ていると、同じ嘘解法で AC している人がたくさんいた感じだった。
問題概要
文字列 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"); }