//0-indexedと1-indexedの変換に混乱。 // //a[i] = 先頭i文字に含まれる「(の数 - )の数」とする。 //言い換えると、a[i] = 1~i番目の文字に含まれる「(の数 - )の数」。 //ここで、K番目の文字が(ならば、a[K] == a[i] - 1(K < i)を満たすような最小のiが答え //K番目の文字が)ならば、a[K] == a[i] + 1(K > i)を満たすような最大のiが答え //となる。(補足:a[i] == a[j]となるとき、s[i]とs[j]は同じ深さにいる) #include #include using namespace std; int main() { int n, k; string s; int i; cin >> n >> k >> s; int a[10001] = {0}; for( i = 1; i <= n; i++ ) a[i] = a[i - 1] + (s[i - 1] == '(' ? 1 : -1); //i(>=1)文字目はs[i-1]に格納されている /*for( i = 0; i <= n; i++ ){ cout << "a[" << i << "] = " << a[i] << endl; }*/ if( s[k - 1] == '(' ){ for( i = k + 1; i <= n; i++ ) if( a[i] == a[k] - 1 ) break; cout << i << endl; } else { for( i = k - 1; i >= 0; i-- ) if( a[i] == a[k] + 1 ) break; cout << i << endl; } return 0; }