Kazun の競プロ記録

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

AtCoder Beginner Contest 237 D 問題 LR insertion

AtCoder ABC ABC237 D問題 400 pts

問題

提出解答

問題の概要

数列 $A=(0)$ と長さ $N$ の ${\tt L}, {\tt R}$ からなる文字列 $S$ が与えられる. 以下を $i=1,2, \dots, N$ の順に処理し, 完成する数列を求めよ.

$S_i={\tt L}$ ならば, $A$ にある $i-1$ のすぐ左に $i$ を挿入する.
$S_i={\tt R}$ ならば, $A$ にある $i-1$ のすぐ右に $i$ を挿入する.

制約

$1 \leq N \leq 5 \times 10^5$
$|S|=N$
$S$ は ${\tt L}, {\tt R}$ からなる文字列

解法

この問題の解答は, 以下の問題の解答と同じである.

数列 $B=(N)$ と長さ $N$ の ${\tt L}, {\tt R}$ からなる文字列 $S$ が与えられる. 以下を $i=N,N-1, \dots, 2,1$ の順に処理し, 完成する数列を求めよ.

$S_i={\tt L}$ ならば, $B$ の先頭に $i-1$ を挿入する
$S_i={\tt R}$ ならば, $B$ の末尾に $i-1$ を挿入する.

この問題を解くためには, 両側キューというデータ構造を利用することにより, 計算量 $O(N)$ で求めることができる.