Kazun の競プロ記録

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

AtCoder Beginner Contest 299 C問題 Dango

AtCoder ABC ABC299 C問題 300 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$L$ を正の整数とする. このとき, 文字列 $T$ がレベル $L$ のダンゴ文字列であるとは, 以下の条件を全て満たすことである.

$T$ は長さ $(L+1)$ である.
$T$ の先頭と末尾のうち, どちらか一方のみが ${\tt -}$ であり, 残りの $L$ 個の文字は ${\tt o}$ である.

長さ $N$ の ${\tt o}, {\tt -}$ からなる文字列 $S$ が与えられる. 次の条件を満たす正の整数 $X$ は存在するか? 存在するならば, 条件を満たす $X$ の最大値を求めよ.

$S$ の連続する部分列のうち, レベル $X$ のダンゴ文字列が存在する.

制約

$1 \leq N \leq 2 \times 10^5$
$S$ は ${\tt o}, {\tt -}$ からなる長さ $N$ の文字列

解法

$S$ に ${\tt o}, {\tt -}$ のどちらか一方しか存在しないとき, これは明らかにダンゴ文字列になる部分列は存在しない.

よって, $S$ には ${\tt o}, {\tt -}$ の両方が存在すると仮定しても良い. このとき, $S$ は連続部分列として ${\tt o-}, {\tt -o}$ のうち少なくとも一方を含むので, $X=1$ は条件を満たす.

$S$ を ${\tt -}$ で区切ったとき, 各区画における ${\tt o}$ の数を左から順に $p_0, \dots, p_k$ とする *1.

$p=\max (p_0, \dots, p_k)$ として, $p=p_j$ とする. このとき, $S$ に ${\tt o}, {\tt -}$ の両方を含むという仮定から, $X \leq p$ であるような任意の正の整数 $X$ に対して, $p_j$ を担う区間において, 左端 $X$ 個または右端 $X$ 個の ${\tt o}$ を用いることにより, レベル $X$ のダンゴ文字列を構成できる.

また, $X \gt p$ であるような任意の正の整数 $X$ に対して, $S$ には $X$ 個連続する ${\tt o}$ の連続部分列は存在しない.

以上から, 答えは $p$ である. この $p$ はランレングス圧縮を利用することによって, $O(N)$ 時間で求められることができる.

*1:例: $S={\tt o--oo-}$ のときは $p=(1,0,2,0)$ である.