C - 仲良し文字列 Editorial by noimi
\(A\) と \(B\) に含まれる文字の多重集合が一致していないときは明らかに NO です。
また、\(A\) と \(B\) の文字が異なるようなインデックスが \(6\) つより多く存在する場合も明らかに構成できません。 以下ではこれらの条件は満たされているものとして考えます。
\(A\) と \(B\) の文字が異なるようなインデックスのみを取り出した文字列をそれぞれ \(\bar{A}, \bar{B}\) とします。 文字数が \(6\) 文字以下と少ないため、何回の swap でこれらが一致することがあるかは全探索することができます。
ところで、同じ操作を二回連続で行うと状態は操作前に戻ります。これを用いると、\(k\) 回で一致させることができれば、 \(k+2\) 回でも一致させられることがわかります。
\(\bar{A},\bar{B}\) が \(3\) 回以内では一致しなかった場合は NO です。上の考察より、\(1\) 回で一致した場合は \(3\) 回でも一致させることができます。 よって、考えるべきは \(0, 2\) 回で一致した場合です。
以下のように場合分けをして考えます。
\(A\) 内に同じ文字が存在するとき
- この時、\(3\) 回に満たない回数だけその文字同士を swap すれば \(3\) 回の場合が構成できることがわかります。
\(A\) 内の文字がすべて相異なるとき
- 置換の偶奇を考えると、\(3\) 回で一致させることはできないことがわかります。
posted:
last update: