AtCoder Beginner Contest 268 G問題 Random Student ID

問題

提出解答

問題の概要

$\mathcal{A}$ を英小文字全体からなる集合とする. つまり, $\mathcal{A}=\{ {\tt a}, \dots, {\tt z} \}$ である. また, $\mathcal{O}$ を $\mathcal{A}$ の全順序全体の集合とする.

$N$ 個の相異なる英小文字列 $S_1, \dots, S_N$ がある. $\mathcal{O}$ からランダムに全順序 $\leq \in \mathcal{O}$ からを1つ選び, $\leq$ に従う辞書式にこの $N$ 個の文字列を並び替えることを行う.

このとき, $i=1,2, \dots, N$ それぞれについて, $S_i$ の順位の期待値を求めよ.

制約

$2 \leq N$
$S_i$ は英小文字からなる非空の文字列
$S_1, \dots, S_N$ は互いに異なる.
$\displaystyle \sum_{i=1}^N |S_i| \leq 5 \times 10^5$

解法

非空文字列 $S,T$ と全順序 $\leq \in \mathcal{O}$ に対して, $P(\leq , S, T)$ を $\leq$ に従う辞書式順序において, $S$ が $T$ 以上ならば $1$ , $S$ が $T$ 未満ならば $0$ であるとする.

このとき, 全順序 $\leq \in \mathcal{O}$ を一つ固定したとき, $N$ 個の文字列 $S_1, \dots, S_N$ の順位 $R_i$ は

$\displaystyle R_i=\sum_{j=1}^N P(\leq, S_i, S_j)$

であるから, 期待値 $E_i=E[R_i ]$ は

$\displaystyle \begin{align} E_i &=\sum_{\leq \in \mathcal{O}} \dfrac{1}{|\mathcal{O}|} R_i \\ &=\dfrac{1}{|\mathcal{O}|} \sum_{\leq \in \mathcal{O}} \sum_{j=1}^N P(\leq, S_i, S_j) \\ &=\dfrac{1}{|\mathcal{O}|} \sum_{j=1}^N \sum_{\leq \in \mathcal{O}} P(\leq, S_i, S_j) \\ &=\dfrac{1}{|\mathcal{A}|!} \sum_{j=1}^N \sum_{\leq \in \mathcal{O}} P(\leq, S_i, S_j) \\ \end{align}$

ここで, 非空英文字列 $S,T$ に対して, $L(S,T)$ を

$\displaystyle L(S,T):=\sum_{\leq \in \mathcal{O}} P(\leq, S,T)$

と定めると,

$\displaystyle E_i=\dfrac{1}{|\mathcal{A}|!} \sum_{j=1}^N L(S_i, S_j)$

である.

このとき, $L(S,T)$ は次の数を表している.

$\mathcal{A}$ の全順序のうち, それに従う辞書式順序において, $S$ が $T$ 以上になる全順序の数.

$L(S,T)$ を求めることにする.

$1 \leq k \leq \min (|S|, |T|)$ で $S_k \neq T_k$ となる整数 $k$ が存在する場合,

$k:=\min \{ k \mid 1 \leq k \leq \min (|S|, |T|), S_k \leq T_k \}$

とすると, $S,T$ の順序は $S_k, T_k$ の順序に一致する. よって, $L(S,T)$ は $S_k$ が $T_k$ よりも大きくなる全順序の数なので,

$L(S,T)=\dfrac{|\mathcal{A}|!}{2}$

である.

任意のでである場合.
- $|S| \lt |T|$ ならば, $S$ は $T$ の (真の) prefix であるから, 任意の全順序で $S$ は $T$ より小さくなる. よって, $L(S,T)=0$ である.
- $|S| =|T|$ ならば, $S=T$ であるから, 任意の全順序で $S$ は $T$ 以上 (正確にはイコール) である. よって, $L(S,T)=|\mathcal{A}|!$ である.
- $|S| \gt |T|$ ならば, $T$ は $S$ の (真の) prefix であるから, 任意の全順序で $S$ は $T$ より大きくなる. よって, $L(S,T)=|\mathcal{A}|!$ である.

$S$ が $T$ の真の prefix であり, その時に限り $S \lhd T, T \rhd S$ と書くことにすると,

$L(S,T)=\begin{cases} 0 & (S \lhd T) \\ |\mathcal{A}|! & (S=T \lor S \rhd T) \\ \dfrac{|\mathcal{A}|!}{2} & ({\rm otherwise}) \end{cases}$

である.

ここで, $A_i, B_i$ をそれぞれ

$A_i:=\{j \mid 1 \leq j \leq N, S_i \lhd S_j \}$
$B_i:=\{j \mid 1 \leq j \leq N, S_i \rhd S_j \}$

とする. つまり, $A_i$ は $S_1, \dots, S_N$ にある $S_i$ を真の prefix にする文字列の数, $B_j$ は $S_1, \dots, S_N$ にある $S_i$ の真の prefix の数である..

すると, $S_1, \dots, S_N$ は互いに異なることから,

$\begin{align} E_i &=\dfrac{1}{|\mathcal{A}|!} \sum_{j=1}^N L(S_i, S_j) \\ &=\dfrac{1}{|\mathcal{A}|!} \left(0 \times A_i+|\mathcal{A}|! \times (B_i+1)+\dfrac{|\mathcal{A}|!}{2} \times (N-(A_i+(B_i+1))) \right) \\ &=\dfrac{1}{2} ( (N+1)-(B_i-A_i) ) \\ \end{align}$