B → \(1\) , G → \(2\) , R → \(3\) と置き換えて、\((1, 2, 3)\) の並べ替えの問題として解説します。

\((1, 2, 3)\) の並べ替えには、

• \((1, 2, 3)\)
• \((1, 3, 2)\)
• \((2, 1, 3)\)
• \((2, 3, 1)\)
• \((3, 1, 2)\)
• \((3, 2, 1)\)

の \(6\) 種類があります。\(1\) 回の操作でどれからどれへ変換することができるかを図に表すと、以下のようになります。

これを見ると、並べ替えを \(2\) つのグループに分けられることがわかります。

• グループ A : \((1, 2, 3), (2, 3, 1), (3, 1, 2)\)
• グループ B : \((1, 3, 2), (2, 1, 3), (3, 2, 1)\)

グループ A の要素からは \(1\) 回の操作でグループ B の要素に、グループ B の要素からは \(1\) 回の操作でグループ A の要素に変換することができるので、\(10^{18}\) 回の操作で \(S\) を \(T\) にすることができるかは、\(S\) と \(T\) が同じグループであるかどうかを判定すれば良いです。

一般化

さて、\(3\) 要素の並べ替えではなく、\(n\) 要素であった場合はどうすれば良いでしょうか。ここで登場するのが、転倒数 です。

転倒数は、\((1, 2, \dots, n)\) の並べ替え \((A_1, A_2, \dots, A_n)\) に対して、 \(i < j\) かつ \(A_i > A_j\) であるような整数の組 \((i, j)\) の数として定義されます。そして、転倒数が偶数であるような並べ替えを 偶置換 、転倒数が奇数であるような並べ替えを 奇置換 と呼びます。これが先ほどの \(2\) つのグループと対応します。偶置換に \(1\) 回の操作を行うと必ず奇置換に、奇置換に \(1\) 回の操作を行うと必ず偶置換になるので、どんなに大きい偶数回の操作を行なっても、違うグループに変換することはできないのです。

奇置換・偶置換のテクニックは ARC などでも頻出のテクニックですので、覚えておくと良いでしょう。

実装例 (C++)

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

bool sign(string S){
    return S == "R G B" || S == "G B R" || S == "B R G";
}
int main(){
    string S, T;
    getline(cin, S);
    getline(cin, T);
    if(sign(S) == sign(T)) cout << "Yes" << endl;
    else cout << "No" << endl;
}

実装例 (Python)

A = ["R G B", "G B R", "B R G"]

S = input()
T = input()
print("Yes" if (S in A) == (T in A) else "No")