注意

このような問題は構文解析というジャンルに含まれます。この問題においても、他の多くの問題と同じように直接文字列をパースすることで解くことができます。BNF 記法にそのまま従って、再帰関数を用いて文字列を解析するのが簡単です。

まとめ

天下り的ですが、結論を先に述べます。

\(F(N)\) として持つべき状態は、組 \((a, b, \varepsilon)\) として表せます。ただし、 \(a, b\) は負でない整数、 \(\varepsilon\) は \(0, 1\) のいずれかです。 \(\varepsilon\) は直感的に「発散の速度が \(\log(N)\) に及ばないが、 \(N \to \infty\) とするとそれが \(\infty\) に発散するもの」を表します。

そうすると、問題の答えは \(\varepsilon = 0\) なら \((a, b)\) 、 \(\varepsilon = 1\) なら \((a, b+1)\) となります。

状態の大小を辞書順で定義します。つまり、

• \((a_1, b_1, \varepsilon_1) \ge (a_2, b_2, \varepsilon_2)\) であるための必要十分条件が、 \(a_1 > a_2\) または（ \(a_1 = a_2\) かつ \(b_1 > b_2\) ）または（ \(a_1 = a_2\) かつ \(b_1 = b_2\) かつ \(\varepsilon_1 \ge \varepsilon_2\) ）

とします。

1. まず、 \(m\) を正の整数とすると \(N^m\) の状態は \((m, 0, 0)\) です。

2. \(F_1(N), F_2(N)\) の状態をそれぞれ \((a_1, b_1, \varepsilon_1), (a_2, b_2, \varepsilon_2)\) とします。\(F_1, F_2\) の和と積の状態は次のようになります。

   • \(F_1(N) \times F_2(N)\) の状態は \((a_1 + a_2, b_1 + b_2, \varepsilon_1 ~ \mathrm{OR} ~ \varepsilon_2)\)
   • \(F_1(N) + F_2(N)\) の状態は \(\max\{(a_1, b_1, \varepsilon_1), (a_2, b_2, \varepsilon_2)\}\)

3. \(F(N)\) の状態を \((a, b, \varepsilon)\) とすると、 \(m\) を正の整数として \((\log(F(N)))^m\) の状態は次のようになります。

   • \(a > 0\) なら \((0, m, 0)\)
   • \(a = 0\) なら \((0, 0, 1)\)

よって、再帰を行いながら文字列をパースすることでこの問題を解くことが出来ます。ただし、問題の制約において \(a, b\) の値は 32bit 整数型に収まらないことがあることに注意してください（64bit 整数型には収まります）。

証明のまとめ

\(0 < \displaystyle \lim_{N \to \infty} \frac{F(N)}{N^a(\log N)^b} < \infty\) のとき、 状態を \((a, b, 0)\) とします。

\(\displaystyle \lim_{N \to \infty} \frac{F(N)}{N^a(\log N)^b} = \infty\) であり、さらに、ある \(t > 0\) が存在して

\[ \displaystyle \lim_{N \to \infty} \frac{F(N)}{N^a(\log N)^{b}(\log (\log N))^t} = 0 \]

となるとき、状態を \((a, b, 1)\) とします。

実は、入力で与えられる \(F(N)\) はこの \(2\) 種類しかないことが（あとに）示されます。以下の証明により、数学的帰納法的に、ある長さ以下の文字列で表される関数 \(F(N)\) には「状態」がただ \(1\) つ存在することが分かります。

証明・考察

はじめに

\(N \to \infty\) のとき、入力で与えられる \(F(N)\) は \(N \to \infty\) で無限大に発散します。よって、問題の極限値は \(0\) 以上としてよいです。

問題の極限 \(\displaystyle \lim_{N \to \infty} \frac{F(N)}{N^a(\log N)^b}\) が有限値に収束するという条件は、ランダウの \(O\) 記法に非常に似ています。 \((a, b)\) は直感的に「無限大に発散する速さ」を表します。いま、 \(\log N\) は \(N\) より発散が遅く、 \(\log (\log N)\) は \(\log N\) より発散が遅いと言うことができます。これは、

\[ \begin{aligned} \displaystyle \lim_{N \to \infty} \frac{\log N}{N} = 0\\ \lim_{N \to \infty} \frac{\log (\log N)}{\log N} = 0 \end{aligned} \]

であるためです。さらに、\(N, \log N, \log(\log N)\) に対する ad-hoc な評価として、任意の正の実数 \(c > 0\) に対して

\[ \begin{aligned} \displaystyle \lim_{N \to \infty} \frac{(\log N)^c}{N} = 0\\ \lim_{N \to \infty} \frac{(\log (\log N))^c}{\log N} = 0 \end{aligned} \]

も成り立ちます。

証明

$x$ を実数として $\displaystyle \lim_{x \to \infty} \frac{(\log x)^c}{x} = 0, \lim_{x \to \infty} \frac{(\log (\log x))^c}{\log x} = 0$ を示せばよいです。いま、 $t = \log x$ とすると、 $x \to \infty$ なら $t \to \infty$ で、 $x = e^t$ に注意します。 $c$ より大きい整数を $m$ とすれば、 $$ \begin{aligned} \displaystyle e^t = 1 + t + \frac{1}{2!}t^2 + \frac{1}{3!}t^3 + \cdots + \frac{1}{m!} t^m + \cdots \ge \frac{1}{m!} t^m \end{aligned} $$ であるので、 $$ \begin{aligned} \displaystyle \lim_{x \to \infty} \frac{(\log x)^c}{x} &= \lim_{t \to \infty} \frac{t^c}{e^t}\\ &\le \lim_{t \to \infty} \frac{t^c}{t^m} m!\\ &= \lim_{t \to \infty} \frac{1}{t^{m-c}} m!\\ &= 0 \end{aligned} $$ となります。一方、 $\log x$ と $x$ はともに正なので、 $\displaystyle \lim_{x \to \infty} \frac{(\log x)^c}{x} \ge 0$ です。よって、はさみうちの原理により $$ \begin{aligned} \displaystyle \lim_{x \to \infty} \frac{(\log x)^c}{x} = 0 \end{aligned} $$ が示されました。 $\displaystyle \lim_{x \to \infty} \frac{(\log (\log x))^c}{\log x} = 0$ については、 $\displaystyle \lim_{x \to \infty} \frac{(\log x)^c}{x} = 0$ において $x \mapsto \log x$ と置き換えれば得ることができます。

これは、「 \(\log N\) を何乗しても \(N\) の発散の速さには及ばない 」「 \(\log (\log N)\) を何乗しても \(\log N\) の発散の速さには及ばない 」というふうに直感的に思うことができます。

考察1. \(F(N)\) の状態が \((a, b, 0)\) であるときの加算・乗算

\(F_1(N)\) と \(F_2(N)\) の状態を、それぞれ \((a_1, b_1, 0), (a_2, b_2, 0)\) とします。このとき、

• \(F_1(N) \times F_2(N)\) の状態は \((a_1 + b_1, a_2 + b_2, 0)\)
• \(F_1(N) + F_2(N)\) の状態は \(\max\{(a_1, b_1, 0), (a_2, b_2, 0)\}\)

になります。

$F_1(N) \times F_2(N)$ の証明

$\displaystyle \lim_{N \to \infty} \frac{F_1(N)}{N^{a_1}(\log N)^{b_1}} = c_1\ (>0)$ 、 $\displaystyle \lim_{N \to \infty} \frac{F_2(N)}{N^{a_2}(\log N)^{b_2}} = c_2\ (>0)$ とします。 $F_1, F_2$ の積と和を考えます。 $F_1(N) \times F_2(N)$ について、 $$ \begin{aligned} \displaystyle \lim_{N \to \infty} \frac{F_1(N) \times F_2(N)}{N^{a_1 + a_2}(\log N)^{b_1 + b_2}} &= \lim_{N \to \infty} \frac{F_1(N) \times F_2(N)}{N^{a_1}(\log N)^{b_1} \times N^{a_2}(\log N)^{b_2}}\\ &= \lim_{N \to \infty} \left(\frac{F_1(N)}{N^{a_1}(\log N)^{b_1}} \times \frac{F_2(N)}{N^{a_2}(\log N)^{b_2}}\right)\\ &= \left(\lim_{N \to \infty} \frac{F_1(N)}{N^{a_1}(\log N)^{b_1}}\right) \times \left(\lim_{N \to \infty} \frac{F_2(N)}{N^{a_2}(\log N)^{b_2}}\right)\\ &= c_1 \times c_2\\ \end{aligned} $$ が成り立ちます。 $0 < c_1 \times c_2 < \infty$ なので、 $F_1(N) \times F_2(N)$ の状態は $(a_1 + a_2, b_1 + b_2, 0)$ となります。

$F_1(N) + F_2(N)$ の証明

$F_1(N) + F_2(N)$ を考えます。 $(a_1, b_1, 0) \ge (a_2, b_2, 0)$ として一般性を失いません。 $(a_1, b_1, 0) = (a_2, b_2, 0)$ の場合、 $$ \begin{aligned} \displaystyle \lim_{N \to \infty} \frac{F_1(N) + F_2(N)}{N^{a_1}(\log N)^{b_1}} &= \lim_{N \to \infty} \left(\frac{F_1(N)}{N^{a_1}(\log N)^{b_1}} + \frac{F_2(N)}{N^{a_1}(\log N)^{b_1}}\right) \\ &= \left(\lim_{N \to \infty} \frac{F_1(N)}{N^{a_1}(\log N)^{b_1}}\right) + \left(\lim_{N \to \infty} \frac{F_2(N)}{N^{a_1}(\log N)^{b_1}}\right) \\ &= c_1 + c_2 \end{aligned} $$ が成り立ち、 $(a_1, b_1, 0) > (a_2, b_2, 0)$ の場合、 $$ \begin{aligned} \displaystyle \lim_{N \to \infty} \frac{F_1(N) + F_2(N)}{N^{a_1}(\log N)^{b_1}} &= \lim_{N \to \infty} \left(\frac{F_1(N)}{N^{a_1}(\log N)^{b_1}} + \frac{F_2(N)}{N^{a_1}(\log N)^{b_1}}\right) \\ &= \left(\lim_{N \to \infty} \frac{F_1(N)}{N^{a_1}(\log N)^{b_1}}\right) + \left(\lim_{N \to \infty} \frac{F_2(N)}{N^{a_1}(\log N)^{b_1}}\right) \\ &= c_1 + 0 \end{aligned} $$ が成り立ちます。 $0 < c_1, c_1 + c_2 < \infty$ なので、結局 $F_1(N) + F_2(N)$ は $\max\{(a_1, b_1, 0), (a_2, b_2, 0)\}$ となります。

考察2. \(F(N)\) の状態が \((a, b, 1)\) であるときの加算・乗算

\(F_1(N)\) と \(F_2(N)\) の状態を、それぞれ \((a_1, b_1, 1), (a_2, b_2, \varepsilon)\) とします。ただし、 \(\varepsilon = 0, 1\) は任意です。

このとき、

• \(F_1(N) \times F_2(N)\) の状態は \((a_1 + b_1, a_2 + b_2, 1)\)
• \(F_1(N) + F_2(N)\) の状態は \(\max\{(a_1, b_1, 1), (a_2, b_2, \varepsilon)\}\)

になります。 \(F_1(N)\) と \(F_2(N)\) の状態がそれぞれ \((a_1, b_1, \varepsilon), (a_2, b_2, 1)\) であったときも同様です。

\(F_1(N) \times F_2(N)\) の証明

\(t_1, t_2 > 0\) であって、

\[ \begin{aligned} \displaystyle \lim_{N \to \infty} \frac{F_1(N)}{N^{a_1}(\log N)^{b_1}(\log (\log N))^{t_1}} = 0\\ \lim_{N \to \infty} \frac{F_2(N)}{N^{a_2}(\log N)^{b_2}(\log (\log N))^{t_2}} = 0 \end{aligned} \]

であるものを \(1\) つとります。（状態の定義によりこのような \(t_1, t_2\) が存在します。また、 \(F_2(N)\) の状態において \(\varepsilon = 0\) であったときも、 \(t_2 = 1\) とすればよいです。）

\(F_1(N) \times F_2(N)\) について、 \(\displaystyle \lim_{N \to \infty} \frac{F_2(N)}{N^{a_2}(\log N)^{b_2}} >0\) （ \(\infty\) の場合も含む）であるので、 ある正の定数 \(r\) があって、整数 \(N_0\) が存在して \(N \ge N_0\) ならば \(\displaystyle \frac{F_2(N)}{N^{a_2}(\log N)^{b_2}} \ge r\) が成り立ちます。よって、

\[ \begin{aligned} \displaystyle \lim_{N \to \infty} \frac{F_1(N) \times F_2(N)}{N^{a_1 + a_2}(\log N)^{b_1 + b_2}} &= \lim_{N \to \infty} \frac{F_1(N) \times F_2(N)}{N^{a_1}(\log N)^{b_1} \times N^{a_2}(\log N)^{b_2}}\\ &= \lim_{N \to \infty} \left(\frac{F_1(N)}{N^{a_1}(\log N)^{b_1}} \times \frac{F_2(N)}{N^{a_2}(\log N)^{b_2}}\right)\\ &\ge \lim_{N \to \infty} \left(r \times \frac{F_1(N)}{N^{a_1}(\log N)^{b_1}}\right)\\ &= \infty\\ \end{aligned} \]

が成り立ちます。さらに、

\[ \begin{aligned} \displaystyle \lim_{N \to \infty} \frac{F_1(N) \times F_2(N)}{N^{a_1 + a_2}(\log N)^{b_1 + b_2} (\log (\log N))^{t_1 + t_2}} &= \lim_{N \to \infty} \frac{F_1(N) \times F_2(N)}{N^{a_1}(\log N)^{b_1}(\log (\log N))^{t_1} \times N^{a_2}(\log N)^{b_2}(\log (\log N))^{t_2}}\\ &= \lim_{N \to \infty} \left(\frac{F_1(N)}{N^{a_1}(\log N)^{b_1}(\log (\log N))^{t_1}} \times \frac{F_2(N)}{N^{a_2}(\log N)^{b_2}(\log (\log N))^{t_2}}\right)\\ &= \left(\lim_{N \to \infty} \times \frac{F_1(N)}{N^{a_1}(\log N)^{b_1}(\log (\log N))^{t_1}}\right) \times \left(\lim_{N \to \infty} \times \frac{F_2(N)}{N^{a_2}(\log N)^{b_2}(\log (\log N))^{t_2}}\right)\\ &= 0 \times 0 = 0\\ \end{aligned} \]

となります。以上から、 \(F_1(N) \times F_2(N)\) の状態は \((a_1 + a_2, b_1 + b_2, 1)\) となります。

\(F_1(N) + F_2(N)\) の証明

\(F_1(N) + F_2(N)\) を考えます。 \((a_1, b_1, 1) \ge (a_2, b_2, \varepsilon)\) である場合、

\[ \begin{aligned} \displaystyle \lim_{N \to \infty} \frac{F_1(N) + F_2(N)}{N^{a_1}(\log N)^{b_1}} &= \lim_{N \to \infty} \left(\frac{F_1(N)}{N^{a_1}(\log N)^{b_1}} + \frac{F_2(N)}{N^{a_1}(\log N)^{b_1}}\right) \\ &\ge \lim_{N \to \infty} \frac{F_1(N)}{N^{a_1}(\log N)^{b_1}} \\ &= \infty \end{aligned} \]

であり、

\[ \begin{aligned} \displaystyle \lim_{N \to \infty} \frac{F_1(N) + F_2(N)}{N^{a_1}(\log N)^{b_1}(\log (\log N))^{t_1 + t_2}} &= \lim_{N \to \infty} \left(\frac{F_1(N)}{N^{a_1}(\log N)^{b_1}(\log (\log N))^{t_1 + t_2}} + \frac{F_2(N)}{N^{a_1}(\log N)^{b_1}(\log (\log N))^{t_1 + t_2}}\right) \\ &= 0 + 0 = 0 \end{aligned} \]

となるため、 \(F_1(N) + F_2(N)\) の状態は \((a_1, b_1, 1)\) です。

\((a_1, b_1, 1) < (a_2, b_2, \varepsilon)\) である場合を考えます。 \(\varepsilon = 0\) のとき、 \((a_1, b_1) < (a_2, b_2)\) であるので、考察 1 と同様になります。 \(\varepsilon = 1\) のとき、 \(F_1\) と \(F_2\) を交換すれば \((a_1, b_1, 1) \ge (a_2, b_2, \varepsilon)\) の場合に帰着します。よって、 \(F_1(N) + F_2(N)\) の状態は \((a_2, b_2, \varepsilon)\) です。

以上から、 \(F_1(N) + F_2(N)\) の状態は \(\max\{(a_1, b_1, 1), (a_2, b_2, \varepsilon)\}\) となりました。

考察 1 と考察 2 より、 \(F(N)\) 同士の加法・乗法は「まとめ」の 2. に示した通りになります。

考察3. \(\log(F(N))\) の挙動

\(F(N)\) の状態が \((a, b, 1)\) であるという定義に、「ある \(t > 0\) が存在して

\[ \displaystyle \lim_{N \to \infty} \frac{F(N)}{N^a(\log N)^{b}(\log (\log N))^t} = 0 \]

が成り立つ」を加えることが出来たのは、ここの挙動のおかげになります。

• \(a > 0\) である場合

この場合、実は \(F(N)\) の状態 \((a, b, \varepsilon)\) の値によらず、\(\log(F(N))\) の状態は \((0, 1, 0)\) になります。

証明

「 $\varepsilon$ - $N$ 論法」を用いて証明します。任意の正の実数 $\varphi > 0$ を固定します。そうすると、 $$ \begin{aligned} \displaystyle \lim_{N \to \infty} \frac{N^{a-\varphi}}{F(N)} &= \lim_{N \to \infty} \left(\frac{N^{a-\varphi} (\log N)^{b}}{F(N)} \times \frac{1}{(\log N)^{b}}\right)\\ &= \lim_{N \to \infty} \left(\frac{N^{a} (\log N)^{b}}{F(N)} \times \frac{1}{(\log N)^{b} N^{\varphi}}\right)\\ &= 0 \times 0 = 0 \end{aligned} $$ となります。よって、ある正整数 $N_1$ が存在して、 $N \ge N_1$ なら $F(N) \ge N^{a-\varphi}$ が成り立ちます。したがって、 $N \ge N_1$ を満たす $N$ において $$ \begin{aligned} \displaystyle \frac{\log(F(N))}{\log N} &\ge \frac{\log(N^{a-\varphi})}{\log N}\\ &= \frac{(a-\varphi) \log N}{\log N}\\ &= a - \varphi \end{aligned} $$ が従います。不等号の逆向きも見ます。 $$ \begin{aligned} \displaystyle \lim_{N \to \infty} \frac{F(N)}{N^{a+\varphi}} &= \lim_{N \to \infty} \left(\frac{F(N)}{N^a (\log N)^{b+1}} \times \frac{(\log N)^{b+1}}{N^{\varphi}} \right)\\ &= \lim_{N \to \infty} \left(\frac{F(N)}{N^a (\log N)^{b+1}}\right) \times \lim_{N \to \infty} \left(\frac{(\log N)^{b+1}}{N^{\varphi}}\right)\\ &= 0 \times 0 = 0 \end{aligned} $$ であるので、ある $N_2$ が存在して、 $N \ge N_2$ なら $F(N) \le N^{a+\varphi}$ が成り立ちます。したがって、 $$ \begin{aligned} \displaystyle \frac{\log(F(N))}{\log N} &\le \frac{\log(N^{a+\varphi})}{\log N}\\ &= \frac{(a+\varphi) \log N}{\log N}\\ &= a + \varphi \end{aligned} $$ が従います。 以上から、 $N_0 = \max\{N_1, N_2\}$ とおけば、 $N \ge N_0$ を満たす整数 $N$ で $$ \begin{aligned} \displaystyle a - \varphi \le \frac{\log(F(N))}{\log N} \le a + \varphi \end{aligned} $$ が成り立ちます。 $\varphi > 0$ は任意であったので、極限の定義より $$ \begin{aligned} \displaystyle \lim_{N \to \infty} \frac{\log(F(N))}{\log N} = a\ (>0) \end{aligned} $$ が示されました。よって、 $\log(F(N))$ の状態は $(0, 1, 0)$ となります。

• \(a = 0\) である場合

この場合、実は \(F(N)\) の状態 \((0, b, \varepsilon)\) によらず、\(\log(F(N))\) の状態は \((0, 0, 1)\) となります。

証明

問題の入力より、 $F(N)$ は定数関数ではなく、 $N \to \infty$ のとき $F(N) \to \infty$ としてよいです。よって、 $$ \begin{aligned} \displaystyle \lim_{N \to \infty} \log(F(N)) = \infty \end{aligned} $$ が成り立ちます。 いま、 $$ \begin{aligned} \displaystyle \lim_{N \to \infty} \frac{F(N)}{(\log N)^{b+1}} = 0 \end{aligned} $$ であるので、ある $N_0$ が存在して、 $N \ge N_0$ なら $F(N) \le (\log N)^{b+1}$ が成り立ちます。したがって、 $$ \begin{aligned} \displaystyle \lim_{N \to \infty} \frac{\log(F(N))}{(\log (\log N))^2} &\le \lim_{N \to \infty} \frac{\log((\log N)^{b+1})}{(\log (\log N))^2}\\ &= \lim_{N \to \infty} \frac{(b+1)\log(\log N)}{(\log (\log N))^2}\\ &= \lim_{N \to \infty} \frac{b+1}{\log (\log N)}\\ &= 0 \end{aligned} $$ です。また、十分大きい $N$ で $\log(F(N)) \ge 0, (\log (\log N))^2 \ge 0$ となります。よって、はさみうちの原理より $$ \begin{aligned} \displaystyle \lim_{N \to \infty} \frac{\log(F(N))}{(\log (\log N))^{2}} = 0 \end{aligned} $$ となります。よって、 $\log(F(N))$ の状態が $(0, 0, 1)$ になることがわかりました。

正の整数 \(m\) について、 \((\log(F(N)))^m\) の状態は、 \(F(N)\) 同士の乗法を繰り返し行うことを考えれば、考察 1, 2 の議論により

• \(a > 0\) のとき \((0, m, 0)\)
• \(a = 0\) のとき \((0, 0, 1)\)

となることがわかります。