A - Right Side Character 解説 by evima
We focus on the last character of the string.
[1] When the last character of \(S\) is A
In this case, it can be shown that the last character of \(f(S)\) is A
. First, it is obvious when \(S={}\)AA...AA
. When \(S\) contains B
, let \(x\) be the maximum \(i\) such that \(S_i={}\)B
. As \(S\) ends with A
, we have \(x\neq N\), and the last character of \(f(S)\) will be \(S_{x+1}={}\)A
. Thus, the claim has been shown.
From this, if we replace a string \(S\) ending with A
with \(f(S)\) \(N-1\) times, it is seen that \(S\) becomes A
.
[2] When the last character of \(S\) is B
When \(S={}\)BB...B
, the answer is clearly B
. Let’s consider \(S\) other than this.
When will the last character of \(f(S)\) be A
for the string \(S\) ending with B
? For that, it is necessary that there is an \(i\) such that \(S_i={}\)B
and \(S_{i+1}={}\)A
. Let’s consider two cases according to whether such an \(i\) exists.
[2-1] If no such \(i\) exists
No such \(i\) exists only when \(S\) is a concatenation of \(x\ (1\leq x)\) A
s and \(y\ (1\leq y)\) B
s. In this case, \(f(S)\) will be a concatenation of \(x-1\) A
s and \(y\) B
s. Specifically, \(f(S)\) also satisfies the following conditions:
- the last character is
B
; - there is no \(i\) such that the \(i\)-th character is
B
and the \(i+1\)-th character isA
.
Therefore, even after replacing \(S\) with \(f(S)\) \(N-1\) times, the last character is B
, and \(S\) becomes B
.
[2-2] If such \(i\) exists
Let \(x\) be the maximum such \(i\). \(S\) is structured as \(S={}\)...BA...ABB...BB
. For \(f(S)\) for such \(S\), let \(y\) be the number of consecutive B
s at the end of \(S\), and the following holds:
- there are exactly \(y-1\) consecutive
B
s at the end of \(f(S)\); - the \(y\)-th character from the end of \(f(S)\) is \(S_{x+1}={}\)
A
; - \(S_{i+1}={}\)
B
for the maximum \(i\) such that \(S_{i}={}\)A
, and thisB
will be in \(f(S)\) as the \(y+1\)-th character or beyond from the end.
From the second and third points, it can be seen that also in \(f(S)\), there is an \(i\) such that the \(i\)-th character is B
and the \(i+1\)-th character is A
. Furthermore, the number of consecutive B
s at the end of \(f(S)\) is one less than that of \(S\). Therefore, if you replace \(S\) with \(f(S)\) \(y\) times, the last character of \(S\) becomes A
.
From this, it can be seen that if we replace such a string \(S\) with \(f(S)\) \(N-1\) times, \(S\) becomes A
.
(Modified the first draft written by GPT-4.)
投稿日時:
最終更新: