\(S\) 及び \(T\) の長さを \(N\) とします．

この問題は，以下のように言い換えることができます．

• \(S\) の \(i\) 文字目 \(S_i\) と \(T\) の \(j\) 文字目 \(T_j\) は，以下の条件の少なくとも \(1\) つを満たす場合に限りペアになることができる．すべての文字が余らないように \(N\) 組のペアを作ることができるかを判定せよ．
  • \(S_i = T_j\)．
  • \(S_i = \) @ であり，かつ \(T_j\) が a,t,c,o,d,e,r のいずれかである．
  • \(T_j = \) @ であり，かつ \(S_i\) が a,t,c,o,d,e,r のいずれかである．

これは，最大二部マッチング問題として考えることができます．\(S\) と \(T\) の各文字を表す頂点を用意して，ペアになれる文字の間に辺を張ったグラフを用意すれば， Hopcroft-Karp のアルゴリズムなどを用いることでこの問題を解くことができます．

しかし，そのまま辺を張ると辺の本数が \(\Theta(N^2)\) となりこの問題の制約では実行時間制限に間に合いません．文字種類が十分少ないことを利用して，\(S\) 側，\(T\) 側それぞれで同じ文字の頂点をまとめることで高速に解くことができます．

解答例(PyPy3): https://atcoder.jp/contests/abc301/submissions/41394540