Kazun の競プロ記録

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

AtCoder Regular Contest 148 B問題 dp

AtCoder ARC148 ARC B問題 500 pts

問題

提出解答

問題の概要

${\tt d}, {\tt p}$ からなる文字列 $T$ に対して, $\overline{T}$ で $T$ を $180$ 度回転させた文字列とする.

${\tt d}, {\tt p}$ からなる長さ $N$ の文字列 $S$ に対して, 以下の操作を高々 $1$ 回行うことができる.

$1 \leq L \leq R \leq N$ なる整数の組 $(L,R)$ を一つ選び, $S$ を $S':=S[:L-1 ] \oplus \overline{S[L:R]} \oplus S[R+1:]$ に置き換える.

最終的な $S$ としてあり得る文字列のうち, 辞書式最小を求めよ.

制約

$2 \leq N \leq 5000$
$S$ は ${\tt d}, {\tt p}$ からなる長さ $N$ の文字列

解法

$S$ が $N$ 個の ${\tt d}$ からなっている場合は明らかに操作しない方がよい.

よって, 以降では $S$ に ${\tt p}$ が含まれているとする. $K$ を一番最初に現れる ${\tt p}$ の添字番号とする. このとき, 以下の事がわかる.

操作をすべきである.
最小にする操作において, $L \leq K$ が成り立つ.

(証明)

$(L,R)=(K,K)$ とすると, $S'$ は $S$ の最初の ${\tt p}$ を ${\tt d}$ に変えることになり, これは $S$ よりも小さい.
$L\gt K$ とすると, $S$ の $K$ 文字目の ${\tt p}$ はそのままであり, 上での操作で出来上がる文字より大きくなってしまう.

また, 次のことも成り立つ.

最小にする操作のうち, $L=K$ であるものが存在する.

(証明)

$L \lt K$ で最小になる操作が存在したとする. このとき, $K$ の定め方から, $S$ の $L$ 文字目から $(K-1)$ 文字目までは全て ${\tt d}$ である. また, $(L,R)=(K,K)$ とした場合の結果を考慮することにより, $S[L:R]$ の末尾 $(K-L+1)$ 文字は全て ${\tt p}$ でなくてはならない. よって, $(L',R')=(K, R-(L-K)$ とした (両端を $(K-L)$ 文字文だけ操作範囲を縮める) 場合と $(L,R)$ の場合の操作の結果が同じである. よって, $L=K$ とした場合でも最小値を求められることが分かった.

よって, $L=K$ とした場合のみを調べればよく, 1回の操作における検証が $O(N)$ 時間であるので, 全体でも $O(N^2)$ 時間で求められることができた.

なお, 最小値を取る $(L,R)$ において, $S[R] ={\tt p}$ であることもわかる.