090 - Tenkei90's Last Problem(★7) Editorial by Nachia


解説

問題文中の条件の \(l,r\) を固定したものを 条件 \((l,r)\) と表すことにします。

条件 \((l,r)\) : \(\mathrm{min} \lbrace A_l,A_{l+1}, \cdots , A_r \rbrace \times (r-l+1) \leq K\)

小課題 1 : $N \leq 10^5 , K = 1$

$A_i \gt K$ なら、条件 $(i,i)$ を満たしません。よって、 $A$ の各要素は $1$ か $0$ です。

条件の式を満たさないのは、 $ \min \{ A_l,A_{l+1},A_r \} = 1$ かつ $r-l+1 \leq 2$ のとき、つまり、数列 $A$ の中で $1$ が $2$ つ以上連続する場合です。よって、求める値は $\mathrm{dp}[\mathrm{P_{os}}][\mathrm{L_{ast}}]$ ( 数列 $A$ の前から $\mathrm{P_{os}}$ 項めまでで、最後が $\mathrm{L_{ast}}$ ) のテーブルを持って $\mathrm{P_{os}}$ の昇順に計算 (DP) すれば求まります。

計算量は $O(N)$ ( $K=1$ に限る) です。

なお、この計算の結果はフィボナッチ数列と同じです。

メッセージ:小課題を考察しよう

IOI などで、 1 つの問題に多数の小課題が用意されることがあります。後の考察のヒントになるものもあれば、元の問題と性質がかなり異なるものもあります。どちらにしても、小課題を取りに行く心掛けは、 1 点を争う競技では欠かせません。

小課題 2 : $N \leq 10^{11} , K = 1$

典型:行列累乗

小課題 1 の解説で示した DP で、 $\mathrm{P_{os}}$ を $1$ 進めるときの遷移は、 線形的 で $\mathrm{P_{os}}$ にかかわらず 一定 です。よって、行列累乗で高速化できます。

計算量は $O( \log N)$ ( $K=1$ に限る) です。

小課題 3 : $N \leq 6 , K \leq 6$

典型: 再帰関数で全探索

数列 $A$ には $K$ より大きい値は存在しません。 ( $A_i \gt K$ は 条件 $(i,i)$ に違反 ) よって、数列 $A$ を最大 $7^6=117649$ 通りに絞れ、全探索が可能です。再帰関数を用いて数列 $A$ を構築するとよいでしょう。

小課題 4 : $N \leq 100 , K \leq 100$

典型: $\min$ の値を決め打ち

条件のうち、 $\min \{ A_l,A_{l+1}, \cdots ,A_r \} = X$ である場合を抜き出すと、条件の式は $$ X \times (r-l+1) \leq K $$ すなわち $$ r-l+1 \leq \lfloor \frac{K}{X} \rfloor $$ となります。この条件は $\min \{ A_l,A_{l+1}, \cdots ,A_r \} \geq X$ としても成り立たなければなりません。

ここから、条件は次のように言い換えられます。

  • $1 \leq X \leq K+1$ について、数列 $A$ に $X$ 以上の値が $\lfloor \frac{K}{X} \rfloor$ 個を超えて連続してはいけない。

この考えは 答えを決め打つ二分探索(Yokan Party) の利点と関係が深いです。例えば、「 $\min \{ A_l,A_{l+1}, \cdots ,A_r \} \geq X$ 」という条件は、「 $A_l,A_{l+1}, \cdots ,A_r$ のいずれも、 $X$ より小さくない」と言い換えることができ、 $X$ との大小関係のみに注目できます。すると、 DP の状態数が指数的に減少したり、貪欲法に持ち込めたりするかもしれません。

解法

値が $X$ 以上の列 $(0 \leq X \leq K)$ は

  • 値が $X+1$ 以上の列
  • 値が $X$ 以上の列,$(X)$,値が $X+1$ 以上の列 を順に連結して得られる列
と表せます。よって、各 $X$ で区間 DP をすることを考えると、 $X$ の大きい順に埋めることができます。それと同時に、長さが $\lfloor \frac{K}{X} \rfloor$ より大きいものを除けばよいです。

数列 $(A_l,A_{l+1},A_{l+2}, \cdots ,A_{r-1})$ としてあり得るものであって、すべての要素が $X$ 以上であるものの数を $\mathrm{dp}[X][l][r]$ とすると、 DP は以下のように計算できます。 $$ \left. \begin{array}{l} \mathrm{dp}[K+1][0][0] = 1 \\ \mathrm{dp}[X][l][r] = \begin{aligned} \left\{ \begin{array}{l} \sum_{m=l}^{r-1} \mathrm{dp}[X][l][m] \cdot \mathrm{dp}[X+1][m+1][r] \hspace{10pt} \\ 0 \hspace{10pt} \end{array} \right. \left. \begin{array}{l} (r-l \leq \lfloor \frac{K}{X} \rfloor) \\ (r-l \gt \lfloor \frac{K}{X} \rfloor) \end{array} \right. \end{aligned} \end{array} \right. $$

計算量は $O( N^3 K )$ です。区間 DP は $ \frac{1}{6} $ の定数倍をもつので、この計算量も定数倍が小さめです。

小課題 5 : $N \leq 10000 , K \leq 10000$

小課題 4 の 解法 において、区間の長さが同じ部分は、数え上げる数列の個数も同じです。よって、単に ( $X$ ,区間の長さ) の組それぞれについて数え上げる DP ができます。

典型: $(\frac{n}{1})^2 + (\frac{n}{2})^2 + (\frac{n}{3})^2 + \cdots + (\frac{n}{n})^2$ は $O(n^2)$

(バーゼル問題より)

DP のテーブルについて、 (区間の長さ) $\leq \lfloor \frac{K}{X} \rfloor$ としてよいです。この部分だけ計算すると、上の典型より計算量は $O((N+K)^2)$ になります。

数列 $A$ に含まれる長さ $n$ の連続部分列としてあり得るものであって、すべての要素が $X$ 以上であるものの数を $\mathrm{dp}[X][n]$ とすると、 DP は以下のように計算できます。 $$ \left. \begin{array}{l} \mathrm{dp}[K+1][0] = 1 \\ \mathrm{dp}[X][n] = \begin{aligned} \left\{ \begin{array}{l} \sum_{m=0}^{n-1} \mathrm{dp}[X][m] \cdot \mathrm{dp}[X+1][n-m-1] \hspace{10pt} \\ 0 \hspace{10pt} \end{array} \right. \left. \begin{array}{l} (r-l \leq \lfloor \frac{K}{X} \rfloor) \\ (r-l \gt \lfloor \frac{K}{X} \rfloor) \end{array} \right. \end{aligned} \end{array} \right. $$

小課題 6 : $N \leq 10^5 , K \leq 10^5$

典型: Inv of Formal Power Series (形式的冪級数の除算)

小課題 5 の DP は、実は形式的冪級数の除算で表せます。 $\mathrm{dp}$ テーブルの $X=p$ ,区間の長さ $=l$ の部分の値を $\mathrm{dp}[p][l]$ とし、 $$ f_p(x) = \sum_{l=0}^{\infty} \mathrm{dp}[p][l] \cdot x^l $$ とします。このとき、 $f_{p-1}(x)$ を求める過程は $$ f_{p-1}(x) = f_p(x) / (1 - x f_p(x)) $$ と表せます。多項式除算の効率的なアルゴリズムを用いて、この式を $O(n \log n)$ $(n = \lfloor \frac{K}{p-1} \rfloor)$ 時間で計算できます。 $998244353$ がNTT素数であることを利用し、畳み込みの手順から NTT を独立させ、一部を省略することで定数倍を改善する方法があります。

「Library Checker」 で verify できます。(https://judge.yosupo.jp/problem/inv_of_formal_power_series)

全体の計算量は $O(N \log N + K \log^2 K)$ です。

小課題 7 : $N \leq 10^{11} , K \leq 10^5$

典型: $K$ -th term of Linearly Recurrent Sequence (線型回帰数列の第 $K$ 項)

小課題 4 で示した条件の $X=0$ の場合に行う計算 $$ f_0(x) = f_1(x) / (1 - x f_1(x)) $$ のみサイズが大きくなりますが、線型回帰数列の計算と同じなので高速化できます。

ボスタン-森法(除算の式から導出される)で $f_0$ の $x^N$ の係数 $(\mathrm{mod} \ 998244353)$ を $O(K \log K \log N)$ 時間で求められます。形式的冪級数の除算と同様、こちらも NTT を独立に用いて定数倍を改善できます。 ボスタン-森法の論文を読むことができます。 (https://arxiv.org/abs/2008.08822)

「Library Checker」 で verify できます。(https://judge.yosupo.jp/problem/kth_term_of_linearly_recurrent_sequence)

全体の計算量は $O(K \log K (\log K + \log N))$ です。

どうしても TLE するときのために
  • $N$ に対して $K$ が十分大きいとき、数列 $A$ が含む複数の異なる値が、制約の内では同じはたらきをします ( 例えば $(N,K)=(5,100)$ のとき、 $0 \leq A_i \leq 20$ は同じはたらきをします ) 。この値はまとめて処理でき、高速化につながる可能性があります。

  • $\mathrm{mod}$ の値 ( $998244353$ ) をプログラム中で静的な定数にすると、関数の引数にするよりも高速になる場合があります。 ( C++(GCC),Java,PyPy3 で確認 )

  • 「Library Checker」 で典型テクニックの実装例を検索できます。

posted:
last update: