Codeforces Round #350 (Div. 2) E. Correct Bracket Sequence Editor
問題文に図があって助かる。
http://codeforces.com/contest/670/problem/E
問題
以下の処理が行えるテキストエディタの動作をシミュレーションせよ。
- カーソルを右に動かす
- カーソルを左に動かす
- カーソル上の括弧と、それに対応する括弧の間を削除する。
削除後のカーソル位置は削除した右括弧のひとつ右で、もし右になにもなければ削除した左括弧のひとつ左とする。
与えられる括弧列は対応がきちんととれている。また不正な操作は与えられず、操作後に空文字列にならないことが保証されている。
- 1≦n,m≦500,000
- 1≦p≦n
n は文字列の長さ。m は操作の数。p はカーソルの初期位置(1-indexed)。
解法
連結リストを使えばいい。愚直に削除しても O(n)。
std::list の erase は削除したノードの次のノードを返す。
Codeforces Round #350 (Div. 2) E. Correct Bracket ...
本番中は std::list の使い方を調べるのが面倒で自作した。std::list はあまり使う機会がないのでよく忘れる。