Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 244 D問題 Swap Hats

AtCoder ABC ABC244 D問題 400 pts

問題

提出解答

問題の概要

${\tt R}, {\tt G}, {\tt B}$ の並び替え $S,T$ が与えられる. 次の操作を $S$ に対してちょうど $10^{18}$ 回行って, $T$ にできるか?

整数 $i,j$ を $1$ 以上 $3$ 以下の異なる整数とする. $S_i, S_j$ を入れ替える.

制約

$S,T$ は ${\tt R}, {\tt G}, {\tt B}$ の並び替え.

解法

2つの要素の入れ替えを $10^{18}$ 回行うということは, $S$ にある偶置換を施して $T$ に一致できるか? という問題を解くことになる.

ここで, $S=(S_1, S_2, S_3)$ に対して, 偶置換を施した結果は

$(S_1, S_2, S_3), (S_2, S_3, S_1), (S_3, S_1, S_2)$

の3個であるので, これらが $T$ に一致するかどうかで判定できる.