Kazun の競プロ記録

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

AtCoder Beginner Contest 242 E問題 (∀x∀)

AtCoder ABC ABC242 E問題 500 pts

問題

提出解答

問題の概要

以下を満たす文字列 $X$ の個数を求めよ.

$X$ は英大文字からなる長さ $N$ の文字列
$X$ は辞書式の意味で $X \leq S$ である回分.

※ $T$ 個のマルチケース

制約

$1 \leq T \leq 2.5 \times 10^5$
$1 \leq N \leq 10^6$
$S$ は英大文字からなる長さ $N$ の文字列
$T$ 個のケースにおける $N$ の総和を $N_{\rm sum}$ とすると, $N_{\rm sum} \leq 10^6$ である.

解法

長さ $M$ の回分は先頭 $L_M:=\lceil \frac{M}{2} \rceil$ 文字が決定すると, 一意に定まってしまう. ここで, $S$ の先頭 $L_N$ 文字の部分列を $\widetilde{S}$ とする.

ここで, 長さが $L_M$ の文字列 $T$ に対して, $f_M(T)$ を

$f_M(T)=\begin{cases} T \oplus \overline{T} & (M: {\rm even}) \\ T \oplus \overline{T'} & (M: {\rm odd}) \end{cases}$

とする. ただし, 文字列 $T,U$ に対して,

$T \oplus U$ で $T,U$ をこの順に連結させた文字列.
$T'$ で $T$ から最後の文字を取り除いた文字列.
$\overline{T}$ で $T$ を逆にした文字列.

とする.

すると, 以下の事がわかる.

任意の長さが $N$ の回分 $U$ はある長さが $L_N$ の文字列 $T$ が存在して, $U=f_N(T)$ となる.
長さが $L_N$ の文字列 $T,U$ において, $T \neq U$ ならば, $f_N(T) \neq f_N(U)$ である.

このことから, 求めるべき場合の数は

長さ $L_N$ の文字列 $T$ の内, $f_N(T) \leq S$ となるような文字列の数

と一致する.

そして, 長さ $L_N$ の文字列 $T$ において,

$T \lt \widetilde{S}$ ならば, $f_N(T) \leq S$
$T \gt \widetilde{S}$ ならば, $f_N(T) \gt S$

であることがわかる. $T \lt \widetilde{S}$ となる長さ $L_N$ の文字列 $T$ の数については, ${\tt A} \to 0, {\tt B} \to 1, \dots, {\tt Z} \to 25$ と置き換えた $26$ 進法としてみることで求めることができる.

残りは $T=\widetilde{S}$ のときの $f_N(T)$ と $S$ との大小関係であるが, これはそのまま愚直に判定することで $O(N)$ 時間で判定できる.

以上から, 答えは $T \lt \widetilde{S}$ となる長さ $L_N$ の文字列の数に, $f_N(\widetilde{S}) \leq S$ ならば $1$ を足した整数となる. 時間計算量は $O(N)$ である.