hotpepsiの練習帳

SRM 688

22:36

https://competitiveprogramming.info/topcoder/srm/round/16709/div/1

Div1 Easy (250)

問題

• 括弧だけの文字列が与えられる
• 閉じ括弧の対応が正しくなるよう、任意の範囲を反転する
• 最大10回反転できるとき、反転する範囲を求める

方針

• (終了後)
• 長さが奇数なら不可能
• 対応関係があるものを除去すると、必ず ))))(( の形になるので、2回反転させればいい
• ただし、閉じ括弧の数と開き括弧の数は一致しないことがある
• 1文字ずつ処理して、対応関係のあるものは消し、そうでないものは元の位置を覚えておく
• 最後の閉じ括弧の位置を覚えてく
• 先頭から最後の閉じ括弧の位置までを反転すると全てが開き括弧になる
• このとき、覚えておいた元の位置の情報も反転する必要がある
• 残った文字列の半分から末尾までを反転すればよい
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_688/ParenthesesDiv1Easy.cpp

結果

--- -1 -25pt 493/xxx rating 1429 -> 1283 (-146)

元の位置を覚えておかなければいけないのが厄介。

http://togetter.com/li/963028