pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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)。

f:id:pekempey:20160507042648p:plain


std::list の erase は削除したノードの次のノードを返す。

Codeforces Round #350 (Div. 2) E. Correct Bracket ...

本番中は std::list の使い方を調べるのが面倒で自作した。std::list はあまり使う機会がないのでよく忘れる。