yukicoder No.22 括弧の対応 解説

問題文

解説

こういう問題はたいていstackを用いる。
今回使う配列
・Pa(vector)
$Pa_i$=$i$と対応しているものの番号。

今回の問題の場合分けは、$s_i$によって決まる。
$s_i$='('のとき→stackにiをpushする。
$s_i$=')'のとき→
$j$=stackの先頭の要素
・$Pa_i$=$j$
・$Pa_j$=$i$
・stackの先頭をpopする。

これを繰り返していき、最後はk番目の要素を求めれば終了。
「与えられる文字列は、すべての文字で括弧の対応があると保証されるとする。」と、問題文の最後に明記されてあるので、わざわざREの対策の場合分けの心配をする必要はない。

C++23での解答例

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n,k;string s;cin>>n>>k>>s;
  stack<int> sta;vector<int> Pa(n);
  for(int i=0;i<n;i++){
    if(s[i]=='(')sta.push(i);
    else{
      int j=sta.top();sta.pop();
      Pa[i]=j;
      Pa[j]=i;
    }
  }
  cout<<Pa[k-1]+1<<endl;
}