[yukicoder] No.691 E869120 and Constructing Array 5

概要

問題文 → ■
公式解説 → ■
自分の提出 → ■

好きな問題です。楽しかったです。

解説で書かれていた方法とは違っていたので、書きます。私は結構難しい問題だと思いました。解けたので、書きます。

解法

小数部分が ${10}^{-n}$ にある程度近いような小数 $x_n$ を適当な方法で作ります。以下のようにしました。

$$\begin{array}{rlrl}{x}_1& =\sqrt{26}& & =5.0990195135927845,\\ x_2& =\sqrt{59}+\sqrt{152}& & =20.00997375380656,\\ x_3& =\sqrt{29}+\sqrt{58}& & =13.000937912998413,\\ x_4& =\sqrt{201}+\sqrt{283}& & =31.00005072001855,\\ x_5& =\sqrt{457}+\sqrt{763}& & =49.000012960298214,\\ x_6& =\sqrt{79}+\sqrt{478}+\sqrt{495}& & =53.00000098767802,\\ x_7& =\sqrt{385}+\sqrt{444}+\sqrt{454}& & =62.00000012871658,\\ x_8& =\sqrt{200}+\sqrt{77}+\sqrt{130}+\sqrt{59}& & =42.00000000998306,\\ x_9& =\sqrt{454}+\sqrt{21}+\sqrt{212}+\sqrt{308}& & =58.00000000096364,\\ x_{10}& =\sqrt{83}+\sqrt{71}+\sqrt{131}+\sqrt{123}+\sqrt{59}+\sqrt{68}& & =56.0000000000936.\end{array}$$

数列の構成

実数 $x$ の小数部分を、$\{x\}$ と書くことにします。

実数 $P$ が与えられたとします。$n_1=\lfloor \frac{\{P\}}{\{x_1\}}\rfloor$ とすると、$P_1=P–n_1{x}_1$ に対して $\{P_1\}<\{x_1\}$ が成り立ちます。$n_2=\lfloor \frac{\{P_1\}}{\{x_2\}}\rfloor$ とすると、$P_2=P_1–n_2{x}_2$ に対して $\{P_2\}<\{x_2\}$ が成り立ちます。

以下、同様にして、$\{P–\sum n_i{x}_i\}<x_{10}<{10}^{-10}$ となる $\{n_i\}$ をとることができます。

$n_i{x}_i$ は、ルートの和で書けることに注意しましょう。例えば $n_2{x}_2=\sqrt{59n_2^2}+\sqrt{152n_2^2}$ となります。これらを合わせると、$29$ 個のルートの和を $P$ から引くことで、$P$ の小数部分を ${10}^{-10}$ 未満にできました。

$n_i<\frac{\{x_{i-1}\}}{\{x_i\}}$ で、$x_i$ はおおよそ $10$ 倍の等比数列にしてあるので、だいたい $n_i<10$ です。$x_i$ は上を見ての通り、$50$ 前後ですから、$\sum n_i{x}_i$ はだいたい $5000$ 以下にはおさまります（ちゃんと計算していないです）。したがって、$29$ 個のルートを引いた結果として、小数部分がとても小さな正の実数が残ります。最後にこれを非負整数（これも非負整数のルート）で近似すれば完成です。

$x_i$ の作り方

適当に探索しましょう。「$\sqrt{1},\dots ,\sqrt{500}$ 等で $3$ つの和を全探索する」 みたいなことをやります。${500}^3$ 個の数が作られるので、誤差 ${500}^{-3}$ くらいの数が見つかることを期待します。$x_7$ まではこうやりました。さらに半分全列挙のテクニックを使って、$4$ つ組と $6$ つ組も探すと、$x_8,x_9,x_{10}$ も作れました。

コメント

$x_i$ の公比の目安 「$10$ 倍」は適当な値です。「$100$ 倍」くらいにすると、数列長の制約は簡単になる一方で $8000$ 以下におさめにくくなるというトレードオフがあります。

$x_4$なんかを見ると分かるように、そんなに ${10}^{-n}$ にきちんと近い必要もないので、パラメータの取り方はとてもたくさんありそうです。ちょうど $30$ 項になったのは偶然でびっくりしました。使うパターンの工夫でまだ減らせると思います。

そもそも $x_2,x_8,x_{10}$ にたまたま $3$ 回現れた $\sqrt{59}$ の寄与をまとめるだけで、$28$ 項が実現できます。このように異なる $x_i$ に同じルートが使われているとオトクです。ルートの中に使う数 $r_i$ を決め打って、$x_k=\sum n_i\sqrt{r_i}$ という形で小数部分を調整すると、さらに項数の少ない構成ができるような気がします。