土下座しながら探索中

主に競技プログラミング

SRM 688 Div1 easy : ParenthesesDiv1Easy

問題概要 :
'('と')'からなる文字列sが与えられる
この文字列に対して次の処理(1,2を連続で)を行うことができる
1. 2つの整数l,r (l<=r)について、 s[l]からs[r]までを反転させる
例 s = "((()", l = 1, r = 3 => s = "((("
2. s[l]からs[r]までの各文字に対して、'('なら')'に、')'なら'('に変更する
例 s = "((()", l = 1, r = 3 => s = "(())"

このとき、文字列sを正しい括弧の対応付けにするまでに必要な処理の内容を出力せよ
ただし、処理は高々10回までとする
正しい括弧の対応付けにできない場合は-1を返すこと
※正しい括弧の例 (), (()), ((()))()(()())

解法 :
処理にどのような特徴があるのか考える
この処理は指定した範囲の部分文字列を単純に反転した後にその中の括弧も反転させる、というもの
そのため、指定した範囲内に存在する正しい括弧は処理を行った後も正しい括弧のままである
例えば、s = "()(", l = 0, r = 3 の処理結果は s = ")()" となる
今後処理をする際に正しい括弧を破壊する意味はないため、正しい括弧は取り除いて考えることができる
例えば、s = "()()()))((((())" は s = ")(((" として考えることができる
正しい括弧を全て取り除いて考えたとき、sのとりうる状態は以下の3通りしか存在しない

1. 全て '('
2. 全て ')'
3. ')' が1つ以上続いた後に '(' が1つ以上続く 例 s = "))))((("

これ以外だと正しい括弧が残っていることになる

結局この3通りだけしかないのであれば、

1. の場合は取り除かれなかった'('の後半分を')'に変換すれば良い
2. の場合は取り除かれなかった')'の前半分を'('に変換すれば良い
3. の場合は取り除かれなかった'('を全て')'に変換 or ')' を全て '(' に変換すると1.か2.の状態になるため上の通りに処理すれば良い

ということになる

     0123456789012345
s = "()()())()((((())"

まず、正しい括弧を取り除く

s = "()()())()( ( (( ())"

     6901
s = ")((("

次に、s を ')' か '(' のどちからのみからなるように変換する
どちらでも良いので今回は ')' だけからなるように変換する

s = ")(((", l = 9, r = 11

s = "))))"

最後に、')'の前半分を'('に変換して正しい括弧の対応付けにする

s = "))))"

s = "(())"

コード :

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
typedef pair<char,int> ci;
const int IINF = INT_MAX;


class ParenthesesDiv1Easy {
public:

  deque<ci> calcDeq(string s) {
    deque<ci> deq;
    rep(i,(int)s.size()) {
      if( s[i] == '(' ) {
        deq.push_back(ci('(',i));
      } else {
        if( (int)deq.size() && deq.back().first == '(' ) deq.pop_back();
        else deq.push_back(ci(')',i));
      }
    }
    return deq;
  }

  string flip(string s,int l,int r) {
    reverse(s.begin()+l,s.begin()+r+1);
    for(int i=l;i<=r;++i) {
      if( s[i] == '(' ) s[i] = ')';
      else              s[i] = '(';
    }
    return s;
  }

  vector <int> correct( string s ) {
    int n = s.size();
    if( n & 1 ) return vector<int>(1,-1);
    deque<ci> deq = calcDeq(s);
    // ()()())()((((()) 
    bool hasL = false, hasR = false;
    int sp = IINF;
    rep(i,(int)deq.size()) {
      if( deq[i].first == '(' ) hasL = true, sp = min(sp,i);
      else                      hasR = true;
    }

    vector<int> ret;
    int len = deq.size();
    if( hasL && hasR ){
      ret.push_back(deq[sp].second);
      ret.push_back(n-1);
      s = flip(s,deq[sp].second,n-1);
      deq = calcDeq(s);
      hasL = false;
    }
    
    if( hasL ) {
      ret.push_back(deq[len/2].second);
      ret.push_back(n-1);
    } else if( hasR ) {
      ret.push_back(0);
      ret.push_back(deq[(int)(len/2)-1].second);
    }
    return ret;
  }
};