A - Right Side Character Editorial by chinerist
末尾の文字に着目します。
[1] \(S\) の末尾の文字が A
のとき
このとき \(f(S)\) の末尾の文字が A
であることが示せます。まず \(S={}\)AA...AA
のときは明らかです。\(S\) が B
を含むとき、\(S_i={}\)B
が成り立つ最大の \(i\) を \(x\) とします。 \(S\) の末尾は A
であることから \(x\neq N\) であり、\(f(S)\) の末尾の文字は \(S_{x+1}={}\)A
になります。以上より示されました。
このことから末尾が A
の文字列 \(S\) を \(N-1\) 回 \(f(S)\) で置き換えると、 \(S={}\)A
になることがわかります。
[2] \(S\) の末尾の文字が B
のとき
\(S={}\)BB...B
のとき、答えは明らかに B
です。以下これ以外の \(S\) について考えます。
末尾が B
の文字列 \(S\) に対し \(f(S)\) の末尾の文字が A
になるのはどのようなときか考えると、\(S_i={}\)B
\(,S_{i+1}={}\)A
をみたす \(i\) が存在していることが必要です。このような \(i\) が存在するかで場合分けしてみます。
[2-1] 上記のような \(i\) が存在しない場合
このような \(i\) が存在しないのは、 \(S\) が A
を \(x\ (1\leq x)\) 文字、B
を \(y\ (1\leq y)\) 文字つなげた文字列になっているときです。このとき、 \(f(S)\) はA
を \(x-1\) 文字、B
を \(y\) 文字つなげた文字列になっています。特に
- 末尾が
B
である - \(i\) 文字目が
B
であり、\(i+1\) 文字目がA
であるような \(i\) が存在しない
という条件は \(f(S)\) も満たします。よって \(S\) を \(N-1\) 回 \(f(S)\) で置き換えた後も末尾の文字は B
であり、\(S={}\) B
になっています。
[2-2] 上記のような \(i\) が存在する場合
上記のような \(i\) の最大値を \(x\) とします。\(S\) は \(S={}\)...BA...ABB...BB
という構造になっています。このような \(S\) に対する \(f(S)\) について、\(S\) の末尾に連続している B
の個数を \(y\) とすると以下が成り立ちます。
- \(f(S)\) の末尾には
B
がちょうど \(y-1\) 個連続している - \(f(S)\) の末尾から \(y\) 文字目は \(S_{x+1}={}\)
A
である - \(S_{i}={}\)
A
をみたす最大の \(i\) に対し \(S_{i+1}={}\)B
であり、これは \(f(S)\) の末尾から \(y+1\) 文字目以降に存在する
\(2\) 番目と \(3\) 番目から、\(i\) 文字目が B
であり \(i+1\) 文字目が A
であるような \(i\) は \(f(S)\) でも存在することがわかります。さらに、\(f(S)\) の末尾に連続している B
の個数は \(S\) とくらべて \(1\) 個減っています。よって \(S\) を \(y\) 回 \(f(S)\) で置き換えると、 \(S\) の末尾の文字は A
になっています。
以上よりこのような文字列 \(S\) を \(N-1\) 回 \(f(S)\) で置き換えると \(S={}\)A
になることがわかります。
posted:
last update: