[Q] F - Transpose
本番出れていないんですが、裏イベントの 第一回マスターズ選手権 -決勝- で遊んでいました。とても良い日で、ごはんも美味しかった。
ABCに出ていた場合、パフォ1600弱で負けです。

考察
1. 直感では()の深いところから処理していくと思ったが、間違い。
どうしても()の文字列をどこかに保存することになり、S^2のデータを扱ってしまうことになる。これは無理。
2. 貪欲的にO(S)で処理が求まるしかなさそう。実際そう。
3. 文字がどのようにつけられていくかシミュレートする

適当なケースを考える
ab(c(de)fg(i)jk)l

処理順番は次のようになる
12 A 89 76 5 43 B
ab(c(de)fg(i)jk)l

答えは次のとおり
123456789AB
abKJiGFdeCl

観察すると
1, 深さが偶数のときは左から右に処理
2. ()がきたときに深さを1つ潜る
3. 深さが奇数のとき、右から左に処理し、文字の大小反転

文字を通過する際に、1文字ずつ確定させていけばいい。

実装

int main() {
  cincout();
  
  string S;
  cin >> S;
  // かっこのペア　英語:parentheses
  vector<ll>parentheses(S.size());
  stack<ll>st;
  rep(i, S.size()){
    if (S[i] == '(') st.push(i);
    else if (S[i] == ')') {
      ll j = st.top(); st.pop();
      parentheses[i] = j;
      parentheses[j] = i;
    }
  }

  string ans;
  auto add_ans = [](string &ans, char c, ll d){
    if (d % 2 == 1){
      // cが小文字なら大文字に
      if (islower(c)) ans += toupper(c);
      else ans += tolower(c);
    }
    else{
      ans += c;
    }
  };

  // dfs(深さ、[開始地点, 終了地点], ans)
  function<void(ll, ll, ll, string&)> dfs=[&](ll d, ll l, ll r, string &ans){
    if (d % 2 == 0){ // 左から右に読んでいく
      for(ll i = l; i <= r; ++i){
        if (S[i] == '('){
          dfs(d + 1, i + 1, parentheses[i] - 1, ans);
          i = parentheses[i]; // かっこの終端に移動
        }
        else{
          add_ans(ans, S[i], d);
        }
      }
    }
    else{ // 右から左に読んでいく
      for (ll i = r; i >= l; --i){
        if (S[i] == ')'){
          dfs(d + 1, parentheses[i] + 1, i - 1, ans);
          i = parentheses[i]; // かっこの先端に移動
        }
        else{
          add_ans(ans, S[i], d); // 大文字小文字を反転
        }
      }
    }
  };
  dfs(0, 0, S.size() - 1, ans);
  cout << ans << endl;
}

https://atcoder.jp/contests/abc350/submissions/52697828