mini notes

競技プログラミングの解法メモを残していきます。

Code Formula 2014 予選B C - 仲良し文字列

問題:C - 仲良し文字列

解答:Submission #10929382 - Code Formula 2014 予選B

解法:1回のスワップでab間の異なる文字が同じになるのは高々2文字なので、7文字以上異なる場合はその時点でNO。6文字であれば3回スワップしても計算量は66=46636で間に合う。なのでスワップ位置で全探索する。

ここで仮にaとbが最初から同じだったとしても、3回はスワップをしないといけないので、スワップ後が必ずしも同じ文字列になるとは限らない。(例:サンプル3)ただし、aの中で同じ文字があると、その文字同士をスワップすることで実質的なスワップ回数を減らすことができる。

よって、aの中に同じ文字があるかないかで何回スワップできるかを変えて全探索すればよい。