yukicoder No.197 手品

★1としては最高難易度に近い気が、と思っていたら★2になっていた。
問題はこちら。

問題

マジシャンのあなたはボールの入ったコップの入れ替えを題材にしたマジックをしようとした。
まずボールが1つ入っているかいないかのコップが3つ用意した。次に右の2つ、または左の2つのコップを入れ替える操作をN回行った。N回の操作後に各コップの中のボールの有無を確認するが、このときのボール有無がN回の操作で実現できないものならマジック成功で、実現可能なら失敗とする。
最初と最後の各コップのボールの有無と操作回数Nを与えられる。マジックは成功したか失敗したかを答えよ。

解法

下の図のように状態数が一番多いパターンでも、2回の操作で任意の実現可能な状態に遷移できるので、それ以上の操作は必要ない。したがってNを3で割った余り2とNのうち小さい方の回数だけシミュレートし、最後の状態がその中にないかどうかを確認すればいい。

oxx ⇔ oxo ⇔ xxo  
|_↑          |_↑  

s1 = raw_input()
N = max(2, int(raw_input()))
s2 = raw_input()
S = set([s1])
while N:
    nS = set([])
    for s in S:
        nS.add(s[0] + s[2] + s[1])
        nS.add(s[1] + s[0] + s[2])
    S = nS
    N -= 1
print "FAILURE" if s2 in S else "SUCCESS"

まとめ

問題解くよりこの記事を書く方がたいへんだった。