Xmas Contest 2018 I: Interesting Equation 解説

https://atcoder.jp/contests/xmascon18/tasks/xmascon18_i

問題概要

実数 $X$ が与えられるので， $\lvert a X^3 + b X^2 + c X + d \rvert$ がだいたい $0$ になるような整数 $a, b, c, d$ を求めよ．

解法 ?

$\lvert a \rvert, \lvert b \rvert, \lvert c \rvert \le 10^4$ なる解の存在が保証されているので，その範囲の $a, b, c$ をすべて調べられれば答えが見つかります．

もちろんそれでは遅すぎるので，半分全列挙のようなことを行いたいです． $a X^3 + b X^2$ の小数部分たち， $c X$ の小数部分たちをそれぞれ列挙すると，ソートして尺取法などを行うことによって答えを探せます．これでも片方は $4 \times 10^8$ 通りほど列挙しなければならないので厳しいですが，何回か提出して $a, b$ の範囲を適当に制限するなどの方法で正解することができるかもしれません (実際，コンテスト中にこのような解法が何件か正解していました)．

解法 1

より均等に分けた半分全列挙を行うことができます．例えば $b = 100 b_1 + b_2$ ( $-100 \le b_1 \le 100$ ， $0 \le b_2 \lt 100$ ) と表すことができ， $a X^3 + 100 b_1 X^2$ の小数部分たち， $b_2 X^2 + c X$ の小数部分たちを列挙します．するとどちらも $10^6$ 程度のサイズとなり，十分高速となります．

チーム aadeeggimrsstuw がこの解法で正解していました．

解法 2

$M$ を十分大きい値として， $\mathbb{R}^4$ の $4$ 本のベクトル

$\begin{align} u_1 &= (1, 0, 0, \lfloor M X^3 \rceil), \\ u_2 &= (0, 1, 0, \lfloor M X^2 \rceil), \\ u_3 &= (0, 0, 1, \lfloor M X \rceil), \\ u_4 &= (0, 0, 0, \lfloor M \rceil) \end{align}$

を考えます ( $\lfloor \alpha \rceil$ は $\alpha$ に最も近い整数とします)．これらの整数係数線型結合であって長さが十分短いものを見つけられれば，それが答えになります：整数 $a, b, c, d$ に対し $a u_1 + b u_2 + c u_3 + d u_4$ の長さが短いとき， $a, b, c$ は小さく， $a X^3 + b X^2 + c X + d$ は $\frac{小さい数}{M}$ くらいなのでだいたい $0$ ，という気持ちです．

「整数係数線型結合で長さが十分小さいもの」を見つける方法として，LLL Algorithm が知られています．詳しい説明は web にいろいろな資料があるので，ざっくりだけ紹介します．

集合 $\mathbb{Z} u_1 + \mathbb{Z} u_2 + \mathbb{Z} u_3 + \mathbb{Z} u_4$ (格子と呼ばれます) を変えないように $u_1, u_2, u_3, u_4$ を変形していきます．変形の操作は次の $2$ 種類からなります：

いい感じの条件を満たすように $u_i$ を並べ替える．
$u_1, u_2, u_3, u_4$ に Gram-Schmidt の直交化を行ったものを $v_1, v_2, v_3, v_4$ とする． $i > j$ に対し， $u_i$ を $u_i - \left\lfloor \frac{\langle u_i, v_j \rangle}{\langle v_j, v_j \rangle} \right\rceil u_j$ で置き換える．

これをいい感じの順番で行うのが LLL Algorithm で，一般の $n$ 次元でも多項式時間で最適解の $2^{\frac{n-1}{2}}$ 倍の長さのベクトルが得られるそうです．すごいですね．一応なぜ直交化したいかの気持ちを説明すると， $\det(u_1, u_2, u_3, u_4)$ は生成する格子にしかよらず (格子の体積)，これは基底が直交していれば長さの積，ななめっていれば長さの積より小さくなっていくので，体積一定では直交に近いほうが長さが短い，という感じです．

この問題では，がんばって評価をすると， $M = 10^{16}$ ととれば制約下で正解が保証できることが示せます (ごちゃごちゃしてしんどいだけなので省略します)．演算は double 等でも大丈夫だと思いますが，多倍長有理数で時間に余裕を持ちつつ正確に行うこともできます．

omeometo さんの解法は，LLL Algorithm の代わりに， $u_i$ を $u_i - \left\lfloor \frac{\langle u_i, u_j \rangle}{\langle u_j, u_j \rangle} \right\rceil u_j$ で置き換えるというのをランダムな $i, j$ を選んでたくさんやっていました．ベクトルが短くなっていく感じはほぼ同じなので，十分な回数回していれば落ちなさそうです．