Kazun の競プロ記録

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

AtCoder Beginner Contest 295 D問題 Three Days Ago

AtCoder ABC ABC295 400 pts D問題

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

問題

提出解答

問題の概要

以下を満たす文字列 $T$ を嬉しい列という. * $T$ のある並び替え $T'$ が存在して, $T'$ は同じ列を $2$ 回繰り返した文字列である.

数字からなる文字列 $S$ が与えられる. 以下を満たす整数の組 $(l,r)$ の数を求めよ.

$1 \leq l \leq r \leq \lvert S \rvert$
$S$ の $l$ 文字目から $r$ 文字目を抜き出した文字列が嬉しい文字列である.

制約

$S$ は数字からなる長さ $1$ 以上 $5 \times 10^5$ 以下の文字列

解法

$N:=\lvert S \rvert$ とする.

数字全体の集合を $U$ とする. つまり,

$U:=\{{\tt 0}, {\tt 1}, \dots, {\tt 9} \}$

である.

ここで, 文字列 $T$ が嬉しい文字列であることと, 任意の文字 $\alpha$ に対して, $T$ に $\alpha$ が出てくる回数が偶数回であることは同値である.

これを利用する. $i=0,1,2, \dots, N$ に対して, $E_i \subset U$ を $S$ の $1$ 文字目から $i$ 文字目を抜き出した文字列において, 奇数回出てくる文字の集合とする. ここで, $E_i$ は以下のようにして求めることができる.

$E_0=\emptyset, \quad E_i=E_{i-1} \triangle \{S_i\} \quad (i=1,2, \dots, N)$

ここで, 集合における対称差は群をなすことから, 累積和の考え方により, 次が同値になることがわかる.

$S$ の $l$ 文字目から $r$ 文字目を抜き出した文字列は嬉しい列である.
$E_{l-1}=E_r$ である.

よって, 次の整数の組 $(l',r)$ を求めれば良いことが分かる *1.

$0 \leq l' \lt r leq N$
$E_{l'}=E_r$

これにより, 正解を導くことができる. 各 $A \subset U$ に対して, [tex; E_0, \dots, E_N] に現れる $A$ の数を $\chi(A)$ と書くことにすると, 求めるべき答えは

$\displaystyle \sum_{A \subset U} \dbinom{\chi(A)}{2}=\sum_{A \subset U} \dfrac{\chi(A)(\chi(A)-1)}{2}$

である.

計算量は $O(N+2^{\# U})$ 時間である.

*1: $l'=l-1$ に対応している