Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 240 D問題 Strange Balls

AtCoder ABC ABC240 D問題 400 pts

問題

提出解答

問題の概要

筒の中にボールを入れていく. 各ボールには $2$ 以上の整数が書かれている. $k$ と書かれたボールが筒の中で $k$ 個連続すると, その $k$ 個は消滅する.

$i$ 番目には $a_i$ と書かれたボールを入れるとき, $i=1,2, \dots, N$ それぞれに対して, $i$ 番目のボールを入れた後に筒の中にあるボールの数を求めよ.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq a_i \leq 2 \times 10^5$

解法

筒の中にあるボールの状況を $[ (b_1, m_1), \dots, (b_r, m_r) ]$ で記録する. ただし, $(b_j, m_j)$ は $b_j$ と書かれたボールがちょうど $m_j$ 個連続していることを意味する. また, $j$ が小さい方が先に入れたほうとする.

このとき, 以下のようにして正解を求めることができる.

$T$ を空列とする.
の順に以下を行う.
- $T$ が空でなく, $b_{|T|}=a_i$ ならば, $m_{|T|}$ に $1$ を加算する.
- (上記を満たさない場合) $T$ が空であるか, $b_{|T|} \neq a_i$ ならば, $T$ の末尾に $(a_i, 1)$ を追加する.
- $b_{|T|}=m_{|T|}$ ならば, $T$ の末尾を取り除く.
- $T$ にある $m_j$ の総和が筒の中にあるボールの個数である.

ここで, 筒の中にあるボールの個数について, $a_i$ のボールを入れた場合, $1$ 個増え, その後消える可能性としてはこのときに入れたボールを含める $a_i$ と書かれたボール $a_i$ 個に限られる.

このことに注意し, Stack というデータ構造を利用することにより, 計算量 $O(N)$ で求めることができる.