Alchemy [Facebook Hacer Cup Qualication Round, Problem B]

　読んだことはないが、鋼の錬金術師のパロディらしい。
　問題文：
Problem B: Alchemy | Facebook Hacker Cup - 2020 - Qualification Round

概要

　奇数個の要素を持つbit列が存在する。その中から連続する３つの要素をのぞき、選んだ３つの要素の中で多い方のbit を持つ要素を除いた箇所に挿入するという操作を繰り返す。

　ただし、選ぶ３つの要素が全て同じbitであることは許されない。
　
　その時、要素が１つになるまで操作を続けることは可能かを判定せよ。

考察

　ゲーム問題なので、後ろから考えてみるが後ろから考えるのは無限にパターンが増えるので厳しい。　
　実験をして考えると、0,1の数の差が１であることと１つにできるかが同値っぽいので、それを証明する。

　証明

十分条件

1回の操作で0,1はそれぞれ１つずつ減るので、0,1の数の差は操作によって不変である。

　最終的に0,1の差は1になるはずなので、0.1 の差が1でないならば、1つにできない。

必要条件

　操作が行えなくなるのは、どの連続する3つの要素を選んでもそれが全て同じbitになる時である。
　しかし、0,1の数の差は操作によって不変であることから、0,1の数の差が1の場合はずっと1であるので要素数が１になるまで必ず操作を行うことができる。

実装

t = int(input())
for case in range(t):
    n = int(input())
    s = input()
    numA = s.count("A")
    numB = s.count("B")
  
    if abs(numA - numB) != 1:
        ans = "N"
    else:
        ans = "Y"
    case_str = "Case #" + str(case + 1) + ":" + ans
    print(case_str)