けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 005 A - STring (300 点)

超定番の stack を使うやつなのんな。類題として

があるのん。これらは見た目は違えど、どれも

"*1()())())()))(())"

のようなカッコ列の整合性に関する問題なん。カッコ列の整合性には以下のような超定番の判定方法があるのん:

  • stack を用意する
  • 左カッコが来たら stack に追加
  • 右カッコが来た時、stack が空だったら「不整合エラー検出」で空じゃなかったら stack にある左カッコと今ある右カッコとをペアにして stack から pop する

こうして最後までやったとき、stack が空なら「整合」していて、stack が空じゃなかったら「不整合」なん。不整合のパターンは

  • 途中で stack が空なのに右カッコが来る
  • 最後に stack に左カッコがあまる

の 2 つがあるのん。

AGC 005 A - STring 問題へのリンク

問題概要

S と T のみで構成された列が与えられる。

  • 文字列中に "ST" のペアがあったら、そのうち一番左にあるものを消す

という操作を繰り返す。最後に残る文字列の長さを求めよ。

制約

  • 1 <= 文字列長 <= 105

解法

冒頭に述べたような stack 処理を行う。修正点として

  • stack が空のときに右カッコが来たら構わず無視

とする。pop される回数をカウントしておいてそれを x とすると答えは「(元の文字列長) - 2x」になる。

なお実装上は、stack は陽に持たず、単純に「左カッコの個数」をカウントするカウンター変数を持っておくだけでよい。

#include <iostream>
#include <string>
using namespace std;

int main() {
  string X; cin >> X;
  int stack = 0, puyo = 0;
  for (int i = 0; i < (int)X.size(); ++i) {
    if (X[i] == 'S') ++stack;
    else if (stack > 0) --stack, ++puyo;
  }
  cout << (int)X.size() - puyo*2 << endl;
}

*1:)((()(