BEN2のブログ

たまに書いています。

ABC 110 C - String Transformation

競技プログラミング

ABC 110 C - String Transformation についてのメモを残します。

この記事、書き直したいとは思っていますが。。。

参考

難しい

問題 : ABC 110 C - String Transformation

  • 入力例 2
chokudai
redcoder

S の 1 文字目 c は r に変換したいので、 c_1 を c に、 c_2 を r にすると、 S は rhokudai になる。
次に S の末尾 i に注目してみる。この i は r に変換したいので、 c_1 を i に、 c_2 を r にすると、 S は ihokudar になる。1 文字目が i になってしまった。
c を r に、i も r に変換しようとしたが出来なかった。
つまり、異なる 2 つ (以上) の英小文字を 1 つの英小文字に変換することはできない。もちろん、1 つの英小文字を異なる 2 つ (以上) の英小文字に変換することもできない。
S から T に変換できる条件は、異なる英小文字は異なる英小文字に変換され、かつ 1 対 1 対応の関係である、らしい ( 解説 PDF )。

  • 入力例 1
azzel
apple

a <--> a z <--> p e <--> l l <--> e の通り、異なる英小文字は異なる英小文字に変換でき、かつ 1 対 1 対応であるため、 S から T に変換することができる。

  • 実装

解説 PDF で説明されている置換表を用意する。ここでは連想配列で実装する。
連想配列 s には S_{i} が T_{i} に置換されることを記録し、 t には T_{i} が S_{i} に置換されることを記録する。 i = 0 から順に記録していく。
もし 1 対 1 対応している場合、 s がキー S_{i} をすでに持っていても s [ S_{i} ] = T_{i} を満たす。 t についても同様。
入力例 2 の t について、1 文字目で t [ {\rm{r}} ] = {\rm{c}} と記録し、2 文字目以降も順次記録していく。末尾の文字を記録するとき、 t はキー {\rm{r}} をすでに持っているが、 t [ {\rm{r}} ] \neq {\rm{i}} であるため、1 対 1 対応とは言えない。

#include <bits/stdc++.h>
using namespace std;

int main() {
  string S, T; cin >> S >> T;
  map<char, char> s, t;
  bool can = true;
  for (int i = 0; i < S.size(); i++) {
    char cs = S[i];
    char ct = T[i];
    if (s.count(cs) && s[cs] != ct) can = false;
    if (t.count(ct) && t[ct] != cs) can = false;
    if (!s.count(cs)) s[cs] = ct;
    if (!t.count(ct)) t[ct] = cs;
  }
  if (can) cout << "Yes" << endl;
  else cout << "No" << endl;
}