Kazun の競プロ記録

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

AtCoder Beginner Contest 284 F問題 ABCBAC

AtCoder ABC284 ABC F問題 500 pts

問題

提出解答

問題の概要

長さ $N$ の英子文字列 $S$ と $0$ 以上 $\lvert S \rvert$ 以下の整数 $i$ 対して, $f_i(S)$ を

$f_i(S)=S[1:i] \oplus \overline{S} \oplus S[i+1:N]$

とする.

ただし,

英子文字列 $X$ の長さを $\lvert X \rvert$ と書く.
英小文字列 $X$ と $1 \leq l,r \leq \lvert X \rvert$ に対して, $X[l:r]$ を $X$ の $l$ 文字目から $r$ 文字目の連続英子文字列とする (ただし, $l \gt r$ の場合は空文字列とする).
2つの英子文字列 $X,Y$ に対して, $X,Y$ をこの順につなげた文字列を $X \oplus Y$ と書く.
英子文字列 $X$ に対して, $X$ を反転させた文字列を $\overline{X}$ と書く.

長さ $2N$ の英小文字列 $T$ が与えられるので, $f_i(S)=T$ となる長さ $N$ の英小文字列 $S$ 及び $0$ 以上 $N$ 以下の整数 $i$ は存在するか? 存在するならばその一例を求めよ.

制約

$1 \leq N \leq 10^6$
$T$ は長さ $2N$ の英小文字列

解法

実は以下が成立する.

$i=0,1,2, \dots, N$ に対して, 以下は同値である.

$f_i(S)=T$ となる長さ $N$ の英子文字列 $S$ が存在する.
$T[1:i] \oplus T[i+N+1:2N]=\overline{T[i+1: i+N]}$

また, このとき, $f_i \left(\overline{T[i+1: i+N]} \right)=T$ である.

よって, 各 $i$ に対して, $T[1:i] \oplus T[i+N+1:2N]=\overline{T[i+1: i+N]}$ かどうかを判定すれば良い.

ただし, 長さが $M$ である2つの文字列の一致判定には一般的に $O(M)$ 時間かかってしまうので, このパートを高速化したい.

これを解決するためにはいくつかの方法があるが, 例えば Rolling Hash によって文字列の一致判定を $O(1)$ 時間にすることができる.

従って, この問題を $O(N)$ 時間で解くことができた.