競技プログラミング

AtCoder AGC 034 B – ABC(600点)

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 600点

問題文

A,B,C からなる文字列 sが与えられます。すぬけ君は sに対して次の操作をできるだけ多く行おうとしています。sの連続した部分文字列であって ABC であるようなものをひとつ選び、 BCA に書き換える。操作回数の最大値を求めてください。

制約

  • 1≦|s|≦200000
  • sの各文字は A,B,C のいずれか

考えたこと

制約からしてO(n)かO(nlogn)で解く問題っぽいです。

そしてうまいことやればsを一回舐めるだけで答えが求まりそうなのでその方針でいくことにしました。

この問題の面倒なところは”ABC”が”BCA”に変わること。つまり変換後に前にも後ろにも”ABC”ができる可能性があります。なので前から舐めても後ろから舐めても安直に行ける方法はなさそうです。

とりあえず前から舐めていくことにします。

前から見て行って”ABC”に遭遇した時に変換を行うわけですが、変換した後今注目しているますより前で”ABC”ができてしまわないか気になります。(後ろはこれから見るので気になりません。)

“ABC”の変換後に前に”ABC”ができるパターンは”AABC”です。このとき2回変換できることになります。同じような感じで”AAABC”だと3回変換できそうです。

じゃあ今注目しているますの前にどれだけ’A’が連続しているかを保持しておけばsを1回舐めればいいのでは?と考え実装して提出してみました。

……

 WA

そんなあ…

とりあえずいろいろ手でテストしてみると、

  • 答えが32bit整数に収まらなさそうなこと
  • “ABCABCABC"を間違えてしまうこと(原因はAが連続している数の数え方が少しおかしかった)

にすぐに気づきました。そこを修正して提出するとACできました。

振り返り

解答では”BC”を’D’に変換してからやってました。確かにその方がミスしにくそう(実際僕もミスしたし…)

答えが32bitに収まらないことは始めの提出前に気づくべきでした。(たぶん”ABCBCBCBC…”だと5*10^9くらいになりそう?)

今回は通らないテストケースを探せばそれがすぐ見つかったのでさくっと通せましたが、これは運によるものなのでもう少し注意して実装したいところです。

ソースコード