AtCoder Beginner Contest 266 の E 問題の解析解

n 問題はこちら

atcoder.jp

で、AC コードはこちら

atcoder.jp

第一引数が float の場合の python の pow 関数の計算量について詳しくないのですが、もし int の場合と同じであれば計算量  O(log(N)) の解答となります。

やっていることは、公式解説をもとに、簡単なさんすうの知識で計算量を改善しているだけです。以下解説。

まずは解説の式を見ていただきつつ、有理数は全順序集合であることから、解説の式は以下の7パターンに書き下せることがわかります。

\begin{align} f(N) = \begin{cases} \frac{7}{2} & (f(N-1) \lt 1) \cr \frac{1}{6} \times f(N-1) + \frac{10}{3} & (1 \leq f(N-1) \lt 2) \cr \frac{1}{3} \times f(N-1) + 3 & (2 \leq f(N-1) \lt 3) \cr \frac{1}{2} \times f(N-1) + \frac{5}{2} & (3 \leq f(N-1) \lt 4) \cr \frac{2}{3} \times f(N-1) + \frac{11}{6} & (4 \leq f(N-1) \lt 5) \cr \frac{5}{6} \times f(N-1) + 1 & (5 \leq f(N-1) \lt 6) \cr f(N-1) & (6 \leq f(N-1) \end{cases} \end{align}

また、漸化式の形から  f(N) が広義単調増加関数であることと、特に  f(N) \lt 6 の範囲においては狭義単調増加関数であること、そして  f(1) = \frac{7}{2} かつ  \displaystyle{\lim_{N \rightarrow \infty} f(N) = 6} から考慮が必要なのは  3 \leq f(N-1) \lt 6 の条件を満たす3つの式だけであることがわかります。

よって  f(N) は以下のように書き下せることがわかります。
漸化式が高々一次方程式である場合簡便な解析式が与えられることは周知の事実であり、かつパラメータの取得手法も有名であり、その手法を使用することで以下の式を得ます。

\begin{align} f(N) = \begin{cases} - \frac{3}{2} \times (\frac{1}{2}) ^ {N - 1} + 5 & (N \leq 2) \cr - \frac{5}{4} \times (\frac{2}{3}) ^ {N - 2} + \frac{11}{2} & (N \leq 5) \cr - \frac{47}{54} \times (\frac{5}{6}) ^ {N - 5} + 6 & (5 \lt N) \cr \end{cases} \end{align}

これを、コードに書き下したものが先述の AC コードとなります。