CS Academy FIICode 2019 Round #3 - Array Macao

• 問題
• AC

しょうもないバグで間に合わなかったのだが、想定解より遅い方法を取ってしまったのでメモしておく。以下、すべて0-basedとし、整数$k$の10進表示に含まれる数字の集合を$D(k)$とする。

$f_A(i, d) = \begin{cases} a_i を末尾とする最長列の長さ & (d \in D(a_i)) \\ 0 & (d \notin D(a_i)) \end{cases} \\ f_B(i, d) = \begin{cases} b_i を末尾とする最長列の長さ & (d \in D(b_i)) \\ 0 & (d \notin D(b_i)) \end{cases}$

とすると、答えは
$\max (\max_{d \in [10]} \max_{i \in [n-1]} f_A(i, d), \max_{d \in [10]} \max_{i \in [n-1]} f_B(i, d))$
であり、漸化式は次のように書ける。

$f_A(i, d) = \begin{cases} 1+ \max_{l \in D(a_i)} \max_{k \in [i-1]} f_B(k, l) & (i \ge 1 かつ d \in D(a_i)) \\ 1 & (i = 0 かつ d \in D(a_0)) \\ 0 & (d \notin D(a_i)) \end{cases} \\$
$f_B(i, d) = \begin{cases} 1+ \max_{l \in D(b_i)} \max_{k \in [i-1]} f_A(k, l) & (d \in D(b_i) かつ第2項\ge 1)\\ 0 & (それ以外)\\ \end{cases}$

$f_A$と$f_B$が微妙に異なるのは、$b_i$を先頭にした列が作れないからである。漸化式の$\max_{k \in [i-1]}f(k, l)$の部分は数字$l$に対応するBITがあれば${\mathcal O}(\log n)$で求まるので、計20本のBITを用意することで全体としては${\mathcal O}(n \log n)$になる。（350msくらいでAC。）

しかし、解説にある通り、以下の通りにDPすれば${\mathcal O}(n)$で求まるはず。

$f_A(k, d) =$ 問題を$\{0, ..., k\}$に制限したとき、末尾が$(a_i)_{i \in [k]}$から選ばれていてかつ数字$d$を含む数であるような最長列の長さ。

$f_B(k, d) =$ 問題を$\{0, ..., k\}$に制限したとき、末尾が$(b_i)_{i \in [k]}$から選ばれていてかつ数字$d$を含む数であるような最長列の長さ。