AtCoder ABC 240 D - Strange Balls (3Q, 茶色, 400 点)

スタックを活用する系の問題！

• 問題へのリンク

問題概要

値 の書かれたボールをこの順に筒に挿入していく。

挿入された際に、同じ数 が 個連続したら、それらがすべて消えるものとする。

個目のボールが挿入された瞬間の、筒内のボールの個数を逐次答えよ。

制約

• 
• 

考えたこと

もし仮に、「同じ数が 個連続したら、消える」という設定　の問題であれば、次のように、単純なスタックの活用で解くことができる。カッコ列整合性判定問題と同じ要領だ。

---

スタックの末尾にボールを順に挿入していく。値 のボールを挿入するとき

• スタックが空であるとき：スタックに値 を挿入する
• 空ではなく、スタックの末尾の要素値が であるとき：その末尾要素を pop する
• 空ではなく、スタックの末尾の要素値が ではないとき：スタックの末尾に値 を挿入する
• 操作後のスタックのサイズを答える

---

同じ数 が 個連続したら消えるとき

それでは、この問題の設定に戻ろう。難しいのは

「値 のボールを新たに挿入したときに、値 のボールが 個連続するかどうか」

を判定する部分だ。これを、毎回スタックを 個遡るのでは、TLE してしまう。そこで、スタックに挿入する値を次のように修正しよう。

---

スタックの各要素を、ペア値 (ボールに書かれた数, その個数) とする

---

こうすることで、値 のボールを新たに挿入したときに、値 のボールが 個連続するかどうかを判定することができる。

全体の計算量は となる。

コード

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

int main() {
    int N, res = 0;
    cin >> N;
    vector<pair<int,int>> st;
    for (int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        if (st.empty() || st.back().first != a) {
            st.push_back({a,1});
            ++res;
        } else { 
            ++st.back().second;
            ++res;
            if (st.back().second == st.back().first) {
                res -= st.back().first;
                st.pop_back();
            }
        }
        cout << res << endl;
    }
}