概要

円環や循環シフトが絡む問題は、もととなる列を $2$ つ繋げて考えることで見通しがよくなることがあります．

問題原案：achapi

解説

長さ $2N$ の数列 $B$ を次のように定めます：

• $B \coloneqq (A_1, A_2, \ldots, A_N, A_1, A_2, \ldots, A_N)$．

すると，この問題は次のように言い換えることができます：

• $B$ の相異なる長さ $N$ の連続部分列であって，辞書順で $K$ 番目に小さいものを求めよ．

また，正整数 $k \; \scriptsize (1 \leq k)$ に対して $S_k, T_k$ を次のように定めます：

• $S_k = (B_k, B_{k+1}, \ldots, B_{k+N})$
• $T_k = (B_k, B_{k+1}, \ldots, B_{2N})$

辞書順の定義を考えると，$S_i < S_j$ ならば $T_i < T_j$ であるので，$S$ が相異なるとすると，$T$ のうち $K$ 番目に小さいものを求める問題に帰着されます．

この問題は，たとえば Suffix Array を用いることで，$\Theta(N \log N)$ 時間などで解決できます．

また，$S_i = S_j \scriptsize \; (i \not= j)$ ならば $T_i$ と $T_j$ の最長共通接頭辞の長さは $N$ 以上であるので，たとえば LCP Array を考えることで，$S_i = S_j$ なる $i, j \scriptsize \; (i \not= j)$ を除外することができます．詳しくは実装例もご参照ください．

解説：uni_kakurenbo

実装例