AtCoder Beginner Contest 242 D問題 ABC Transform
問題
提出解答
問題の概要
からなる文字列
が与えられる. 文字列の列
を以下のようにして生成する.
は
の各文字において,
を
に,
を
に,
を
に同時に置き換えてできる文字列.
次の 個の問
に答えよ.
の先頭から
文字目は何か?
制約
は
からなる文字列
解法
と書くことにする. また, 文字列
と
に対して,
で
の
文字目を表すとする.
まず, であるから, 当然
が成り立つ.
そして, が
のどこから発生しているか? そして,
という構造に気がつくと,
である.
また, 1文字目については上の漸化式から, であることもわかる.
以上から,
となる.
これを計算すればよいのだが, を求めようとすると, 最終的にはある整数
とある非負整数
を用いて,
となるとわかる. 結局はこの
を求めればよく, これから答えるべき文字を求めることもできる.
この は上の漸化式を用いて,
で求めることができる.