Kazun の競プロ記録

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

AtCoder Beginner Contest 259 C問題 XX to XXX

AtCoder ABC ABC259 C問題 300 pts

問題

提出解答

問題の概要

英小文字からなる列 $S,T$ が与えられる. $S$ に対して次の操作を任意回繰り返して, $T$ に一致させることができるか?

$S$ において, 同じ文字が2つ連続しているところの間にその文字を挿入させる.

制約

$S,T$ は長さ $2$ 以上 $2 \times 10^5$ 以下の英小文字列

解法

$S,T$ の Run Length をそれぞれ

$S: ( (c_1, k_1), (c_2, k_2), \dots, (c_n, k_m) )$
$T: ( (d_1, l_1), (d_2, l_2), \dots, (d_m, l_n) )$

とする. このとき, 操作によって $S$ を $T$ に一致させることが可能なことと, 以下は同値である.

$m=n$ .
$i=1,2, \dots, m$ に対して, $c_i=d_i$ .
$i=1,2, \dots, m$ に対して, $k_i=l_i$ または, $(k_i \geq 2$ かつ $k_i \leq l_i)$ .

これを証明する.

十分性: $S$ に対して1回操作を施した文字列 $S'$ に対して上が成り立つことが成り立つことを見れば良い. 上2つについては明らかに成り立つ. 一番下についても操作を施さなかったところのブロックはそのままであり, 施した部分のブロックは元の長さが $2$ 以上であり, 操作によって $1$ 増えるから従う.
必要性: $i=1,2, \dots, m$ に対して, $k_i \lt l_i$ ならば $k_i \geq 2$ であるから, そのブロックに対して $(l_i-k_i)$ 回 $c_i$ を挿入することを行う. これによって $T$ に一致させることができる.

この同値性から $S,T$ の Run Length 圧縮を求め, それらが条件を満たすかどうかを見れば良い. 時間計算量は $O \left(|S|+|T| \right)$ である.