SRM688 div1 easy ParenthesesDiv1Easy

考えたこと

• 文字列長が1000なのに操作回数10回の制限でよくわからない
• とりあえず実験するけどよくわからない
• 括弧列を+1/-1に置き換えるやつをしてみる
• +1/-1の累積和で-1になったところがあったらそこを1回は操作しないとだめ
• 操作しないといけない場所がきたらそこを左端、')'を右端にするような区間で反転しても正しい括弧列になるような区間にしたい
• 条件がかなり厳しいけど操作回数10回で実現するには最適なの操作をしないとだめそうだしとか考える
• 色々実験しても操作回数10回になるようなのは思いつかない
• 75分経ちそうだったので適当な貪欲を書いて投げたら落ちた
  -----解説を見た-----
• 正しい括弧列の部分列は反転しても影響がないから無視
• すると))))))((((((((みたいな列になる
• 前半の')'をひっくり返して後ろ半分を')'に反転すれば正しい括弧列になる
• 2回あれば確実にできる

操作で不変な部分に注目するくらいは思いついてもよかった
操作回数の制限が異様に厳しいんだからきれいな構成が存在する方向でもっと考えるべきだった
あと実装が下手

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

class ParenthesesDiv1Easy {
   public:
   vector <int> correct(string s)
  {
    string ss = s;
    ll n = s.size();
    if(n%2) return {-1};

    vector<ll> x(n);
    REP(i, n) x[i] = (s[i]=='('?1:-1);

    vector<bool> able(n);
    REP(i, n) {
      ll now = 0, idx = -1;
      bool flag = true;
      FOR(j, i, n) {
        now += x[j];
        if(now < 0) flag = false;
        if(flag && now == 0) idx = j;
      }
      FOR(j, i, idx+1) able[j] = true;
    }

    ll idx = -1, cnt = 0;
    REP(i, n) {
      if(able[i]) continue;
      if(s[i] == ')') s[i] = '(', idx = i;
      cnt++;
    }
    if(cnt == 0) return {};

    vector<int> ans;
    if(idx != -1) {ans.PB(0); ans.PB(idx);}

    vector<bool> n_able(n);
    REP(i, idx+1) n_able[i] = able[idx-i];
    REP(i, idx+1) able[i] = n_able[i];

    cnt /= 2;
    for(int i=n-1; i>=0; --i) {
      if(able[i]) continue;
      cnt--;
      s[i] = ')';
      if(cnt == 0) {
        idx = i;
        break;
      }
    }
    ans.PB(idx); ans.PB(n-1);

    return ans;
  }
};