ABC
AGC034-B "ABC"
AGCでABCって問題が出たんですね....w
スマホで一部コード書いたりしてたのでWA連発しました.
というか実行時間すごいギリギリやんけ....
提出コード
考察
左から順になめていきますが,とりあえず"A"以外が来たら問答無用で飛ばしてOK.
Aが来たときですが,例えば
AAABC
みたいなときを考えると,右から順に操作をすることで
AAABC AABCA ABCAA BCAAA
のように変化します.
つまり,"BC"のすぐ左側に連続する"A"がいくつ並んでいるか,というところに着目しました.
連続する"A"が始まったindex(startとします)と,"AAA... BC"で初めて"B"が現れたindex(left_bとします)を持っておきます.
left_bを使って"BC"を"AA"に置き換えた後,startを使って先頭の"AA"を”BC”に置き換え,start+2番目から走査を再開することで求められている操作を実現できます.
この順で操作をすれば,Aが1回しか連続していない文字列(つまり"ABC")でも対応できます.
感想
卒業研究関連のゼミがあったため競プロをするのが久しぶりになってしまいました.
それはさておき,この実装では走査場所が行ったり来たりするためなのか実行時間がギリギリでした.
左側に存在する"A"の数を持っておいて,いいかんじに処理すればもっと高速に動くような気がしなくもないです(?)