Mister雑記

競プロやります。

AGC005-A 「STring」 (300)

典型的な括弧マッチング。

問題リンク

概要

SとTからなる文字列 Xがある。 Xの文字数は偶数で、SとTは同じ数だけ含まれている。

これからこの文字列に対して以下の操作を 10^{10,000}回行う。

  • 最も左にあるSTという連続部分列を消す。
  • このような連続部分列が存在しなければ何もしない。

最終的に残る文字列の長さを求めよ。

制約

  •  2 \leq X \leq 2 \times 10^5

解説

まず無駄に大きい操作回数の 10^{10,000}に意味はなく、消せる文字がなくなったら終了としていい。

操作の回数は高々 |X| / 2回なので、愚直に実装すると計算量は O(|X|^2)で部分点しか取れない。

実のところこの問題、Sを(、Tを)と見なすと典型的な括弧マッチング問題になる。これは以下のようにstackを使うことで O(|X|)で残った長さを判定できる。

  1. stackを用意する。
  2. 文字列を頭から順に見ていく。
    1. 文字が(だった場合、stackにpush。
    2. 文字が)だった場合、
      • stackの末尾が(ならstackからpop。
      • そうでなければ)をstackにpush。
  3. 最終的なstackの要素数が答え。

「頭から順に見ていって、括弧がマッチングしたら即消去」という操作をしている。

なお、上の操作はstackなしでも2つの変数によって実現できる。

  1.  cnt resを0で初期化する。
  2. 文字列を頭から順に見ていく。
    1. 文字が(だった場合、 cntをインクリメント。
    2. 文字が)だった場合、
      •  cnt \gt 0なら cntをデクリメント。
      • そうでなければ resをインクリメント。
  3. 最終的な cnt + resの値が答え。

 cntがstack中の(の数、 resがstack中の)の数を表している。

実装例

#include <iostream>
using namespace std;

int main() {
    string X;
    cin >> X;

    int cnt = 0, res = 0;
    for (char c : X) {
        if (c == 'S') {
            ++cnt;
        } else {
            if (cnt == 0) {
                ++res;
            } else {
                --cnt;
            }
        }
    }

    cout << res + cnt << endl;
    return 0;
}

感想

  • 括弧のマッチングは割とよく出るので解法を覚えて損はない。