Official
\(S\) の先頭の文字が
\(S\) の末尾の文字が
A - AB Palindrome Editorial by nok0
[1] 先頭と末尾の文字に着目する
\(S\) の先頭の文字が A
のとき、これを B
に変化させることは不可能です。
同様に、\(S\) の末尾の文字が B
のとき、これを A
に変化させることは不可能です。
よって、\(S\) の先頭の文字が A
で末尾の文字が B
のとき、\(S\) を回文にすることは不可能です。
以下、\(S\) の先頭の文字が B
、もしくは \(S\) の末尾の文字が A
の場合を考えましょう。
\(S\) の先頭の文字が B
で、\(N\) が \(3\) 以上のとき
\(2,3\) 文字目に対して操作、\(3,4\) 文字目に対して操作、…、とすることで、\(S\) を BAAA…AAAB
という回文にできます。
\(S\) の末尾の文字が A
で、\(N\) が \(3\) 以上のとき
\(N-2,N-1\) 文字目に対して操作、\(N-3,N-2\) 文字目に対して操作、…、とすることで、\(S\) を ABBB…BBBA
という回文にできます。
以上の議論は \(N\) が \(3\) 以上なため成り立っていることに注意してください。\(N=2\) のときは注意する必要があり、\(S\) が BA
のときのみ操作を行っても \(S\) を回文にできません。(AA
、BB
はもとから回文です。)
[2] 本問の解法
結局、以下の条件のいずれかを満たす場合のみ答えは No
で、それ以外の場合答えは Yes
です。
- \(S\) の先頭の文字が
A
で末尾の文字がB
のとき - \(S\) が
BA
のとき
[3] 実装例
Python:
n = int(input())
s = input()
print("Yes" if (s[0] == "B" or s[-1] == "A") and s != "BA" else "No")
posted:
last update: