ゆらのふなびと

競プロ, Python, C++

yukicoder No.197 手品

落ちてたので再挑戦。

問題

No.197 手品 - yukicoder

解法

慎重に場合分けをしていきます。ただし、nは操作回数、s, t はそれぞれ操作前、操作後の文字列とします。

  • s, tでoの個数が異なればありえない
  • (以下、s, tのoの個数は等しい。もしoがxより多ければ、oとxをすべて反転させる。これによりoの個数は0個か1個になる)
  • oが0個(すべて同じ文字)ならあり得る
  • (以下、oは1個である)
  • n == 0のとき、s == t ならあり得る。s != t ならあり得ない
  • n == 1のとき、oが「両方真ん中 or 互いに異なる端」ならあり得ない。そうでなければあり得る
  • n >= 2のとき、あり得る(どの状態にも到達可能)

なんとなくPythonで書いてみました。

def possible(s, t, n):
    if s.count('o') != t.count('o'):
        return False

    if s.count('o') > 1:
        s = s.translate(str.maketrans('ox', 'xo'))
        t = t.translate(str.maketrans('ox', 'xo'))

    if n == 0 or s.count('o') == 0:
        return s == t

    # s.count('o') == 1
    if n == 1:
        return not (s[1] == t[1] == 'o' or s == t[::-1])
    else:
        return True

s = input()
n = int(input())
t = input()
print('FAILURE' if possible(s, t, n) else 'SUCCESS')

落ちたコードは "abs(a - b) == 2" をなぜか "abs(a - b == 2)" と書いていた。