ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

TopCoder SRM 628 Div2 Medium : BracketExpressions

解法・感想など


「Xは最大で5箇所しかこないからXに入る括弧の組み合わせは全部で6^5通りか、5重ループ書いちゃえ」とかやってすみませんでした。

全探索で条件を満たしてるかどうか調べているだけ。

stackを久々に使った感じする。

    • -

355.42 / 500

ソースコード

class BracketExpressions {
public:

  string ifPossible(string expression) {
    string bracket = "()[]{}";
    
    rep(i, 6) rep(j, 6) rep(k, 6) rep(p, 6) rep(q, 6) {
      bool ok = true;
      int count = 0;
      string str = "";
      rep(idx, expression.size()) {
        if(expression[idx] == 'X') {
          if(count == 0) str += bracket[i];
          if(count == 1) str += bracket[j];
          if(count == 2) str += bracket[k];
          if(count == 3) str += bracket[p];
          if(count == 4) str += bracket[q];
          count++;
        }
        else str += expression[idx];
      }
      stack<char> st;
      rep(idx, str.size()) {
        char ch = str[idx];
        if(ch == '(' || ch == '[' || ch == '{') st.push(ch);
        else {
          if(st.empty()) ok = false;
          else {
            string b = "";    
            b += st.top();
            b += ch;
            st.pop();
            if(b == "()" || b == "[]" || b == "{}");
            else ok = false;
          }          
        }
        if(!ok) break;
      }
      if(!st.empty()) ok = false;
      if(ok) return "possible";
    }
    
    return "impossible";
  }
};