2018 codeFlyer 本選 C - 部分文字列と括弧 (500 点)

超定番の「対応がとれている」カッコ列を題材にした問題。

ある文字列が与えられたときにそれが正しいカッコ列かどうか判定するのは、AGC 005 A - STring の方法でできる。

問題へのリンク

問題概要

)()()(((())())()())()()()
のような 文字のカッコ列が与えられる。カッコ列の連続する部分文字列 ( 個ある) のうち、正しく対応がとれているカッコ列が何個あるかを答えよ。

制約

• 

考えたこと

ヒストグラムの最大長方形問題のような stack の使い方をするのが明快そうです。オーダー で解くことができます。

pointer を用意して、

• 左カッコが来たらインクリメント
• 右カッコが来たらデクリメント

するというところまでは普通の カッコ列問題 と同じです。今回の問題を解くために、さらに配列

stack[ pointer ] := その pointer の高さに過去何個の左カッコがあったか

を用意します。配列の pointer を最初 0 (負になりうるので実装上は下駄を履かせます) に設定しておいて、stack[ pointer ] = 1 としておきます。

• 左カッコが来たときは、pointer を進めて (++pointer)、stack[pointer] = 1 と初期化 (過去のその pointer での左カッコはなかったことに)
• 右カッコが来たときは、pointer を下げて (--pointer)、その時点での stack[pointer] を答えに加算して、stack[pointer] をインクリメント

という感じでやるとよさそうです。

#include <iostream>
using namespace std;

const int geta = 110000;
int main() {
  string S; cin >> S;
  int stack[220000] = {0};
  int pointer = geta;
  stack[pointer] = 1;
  long long res = 0;
  for (int i = 0; i < (int)S.size(); ++i) {
    if (S[i] == '(') {
      ++pointer;
      stack[pointer] = 1;
    }
    else {
      --pointer;
      res += stack[pointer];
      ++stack[pointer];
    }
  }
  cout << res << endl;
}