Codeforces Round #594 (Div. 1) B - The World Is Just a Programming Task (Hard Version)

問題ページ
まず，開括弧と閉括弧の数が一致していなければ答えは0である．以下では開括弧と閉括弧の数が一致しているとする．

s=((())())()  
x=1232121010  

次に，与えられた文字列が正しい括弧列でなかった場合を考える．'('が来たら+1，')'が来たら-1をする操作を行う． 番目まで操作を行った値 とする．このとき，最も小さい値になる閉括弧が文字列の右端に来るように巡回シフトを行うことで正しい括弧列に変換することができる．よって，以下では正しい括弧列が与えられるとする．

swapを無視して単に括弧列に対して答えを求める．これは となる の個数を数えればよい．

答えを増やすことができるswapにはどのようなパターンが存在しているのか考える． であるような と対応する に対して操作を行っても答えが改善されることはない． のような括弧列で，3番目と4番目に操作を行って と変換しても，一番外側の括弧の内部でしか括弧列の対応（つまり ）は変動していない．したがって であるような が増えることはない．

したがって， であるような と対応する に対してswapを試せば答えを求めることができる．

• である にswapを行う
  の1番目と6番目をswapすると， となる．この操作を行った結果，2~5番目の括弧が2個とそれ以外に括弧が一つとなった．swapを行った括弧の内部で となる分と，それ以外に括弧が一つという括弧列が得られる．
• である にswapを行う
  の4番目と7番目をswapすると， となる．最初の開括弧と対応する分が1，最後の閉括弧と対応する分が1，swapを行った括弧の内部に存在する分(この例だと1) が答えとなる．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#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()  
template<typename T> bool chmin(T &a, const T &b) { bool r = a>b; a = min(a, b); return r; }  
template<typename T> bool chmax(T &a, const T &b) { bool r = a<b; a = max(a, b); return r; }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll n;  
    string s;  
    cin >> n >> s;  
  
    ll now = 0, mi = 0, idx = -1;  
    REP(i, n) {  
        if(s[i] == '(') ++now;  
        else --now;  
        if(chmin(mi, now)) idx = i;  
    }  
    // '(' と ')' の数が釣り合っていなかったら不可能  
    if(now != 0) {  
        cout << 0 << endl << 1 << " " << 1 << endl;  
        return 0;  
    }  
    // 正しい括弧列でなければ cyclic shift で正しい括弧列にする  
    if(idx != -1) s = s.substr(idx+1) + s.substr(0, idx+1);  
      
    // 正しい括弧列の和に分解  
    auto split = [&](ll l, ll r) -> vector<ll> {  
        if(l >= r) return {};  
        ll now = 0;  
        vector<ll> ret;  
        FOR(i, l, r) {  
            if(s[i]=='(') {  
                if(now == 0) ret.push_back(i);  
                ++now;  
            } else {  
                --now;  
                if(now < 0) return {};  
            }  
        }  
        if(now != 0) return {};  
        return ret;  
    };  
  
    // sを括弧列の和に分解する  
    vector<ll> v = split(0, n);  
    // 実質swapしないパターン  
    ll ans = v.size(), ansl = 0, ansr = 0;  
      
    v.push_back(n);  
    REP(i, v.size()-1) {  
        ll l1 = v[i], r1 = v[i+1];  
        vector<ll> u = split(l1+1, r1-1);  
        u.push_back(r1-1);  
  
        // [v[i], v[i+1]) の両端をswapするパターン x_i=1  
        if(chmax(ans, (ll)u.size())) {  
            ansl = l1;  
            ansr = r1-1;  
        }  
  
        // [v[i], v[i+1]) の内部の括弧の両端をswapするパターン x_i=2  
        REP(j, u.size()-1) {  
            ll l2 = u[j], r2 = u[j+1];  
            vector<ll> w = split(l2+1, r2-1);  
            if(chmax(ans, (ll)w.size()+(ll)v.size())) {  
                ansl = l2;  
                ansr = r2-1;  
            }  
        }  
    }  
  
    if(idx != -1) {  
        (ansl += idx+1 + n) %= n;  
        (ansr += idx+1 + n) %= n;  
    }  
  
    cout << ans << endl << ansl+1 << " " << ansr+1 << endl;  
  
    return 0;  
}  
``