解法
ABCがBCAになるので、これが連鎖的に続くことを考えると、
AAA...BCがBC...AAAになる、もしくはA...BCBCがBCBC...Aになる、の2通りです。
後者のパターンは、前者のパターンをBCが連続している個数だけ繰り返す、とみなすことができるので、今後は無視します。
あとは、文字列を前から見ていき、BCという文字列が現れたときに、その直前にしているAの個数だけ操作が行われ、その後操作を行った部分の末尾が、操作を行った回数だけAが連続している、ということになるので、文字目から順に見ていき、
今見ている文字とその1つ前が
BCになっていない場合
1つ前の文字を調べ、Aなら、連続しているAのカウントを1増やす。そうでなければカウントを0に戻す。今見ている文字とその1つ前が
BCになっている場合
連続しているAのカウントだけ操作を行えるので、答えに追加する。
カウントはそのまま据え置きとする。
次に見る文字は今見ている文字の2つ先とする。
という操作を繰り返していけば、答えを求めることができます。
感想
この問題と少し(?)似ています。
連鎖的に起こるパターンがどうなっているかを丁寧に見ることで、うまく数え上げの条件を探ることができました。
操作の順番が関係ないことを確認するのに時間がかかりました…
