ARC108B Abbreviate Fox - モグリンの競プロ備忘録

長さ $N$ の英小文字からなる文字列 $S$ が与えらえれる。ここから連続部分文字列'fox'を削除する操作を繰り返した時に最後に残る $S$ の最小の長さをこたえよ。

$1 \leq N \leq 2 \times 10^5$

これ茶diffかぁ、沼にハマっちゃってたねぇ。コンテスト中は'fox'を()列に置き換えてみたり、左から貪欲に'f'と'fo'がそれまでに出てきたかどうかでフラグ管理してみたり、色々試してみたけど大事なのは

"愚直な操作を通るようにできないか考えてみる"

ことでしたね。文字列に対する挿入、削除は"末尾を除き"一回当たり $O(N)$ かかりますが末尾に限り $O(1)$ で済むのでなんとか文字列に対する末尾の操作のみでシミュレーションできないか考える。この考え方はABC158 String Formation

とかでもありましたね。今回の場合は

"空文字列 $s$ に対して文字列 $S$ の文字を左から順番に加えていき、文字列'fox'が出てきたら逐次削除する"

という方法で計算量 $O(N)$ で十分高速にシミュレーション可能なんですね、うーん思いつきたかった。

うーん、悔しい。ともあれ

"文字列に対する挿入/追加を何らかの文字列の末尾への処理のみの操作に置き換えることで高速化する"

という自分のなかでの新しい典型を作れたのでよしとしよう、次似たような問題出たらぜって―解く。読んでくれてありがとうございました。

はてなブログって見たまま編集だとソースコード貼り付けられないんすね...。別にこのままでもいい気はするけどせっかくだからどこか機会見つけたらはてな記法の勉強しようかな...。