概要
お誕生日問題
$N$ 元集合 $\{1, 2, \ldots, N\}$ に値を持つ確率変数 $H$ を考える。この確率変数に従うサンプル $h_1, \ldots, h_n$ を、$\exists i\neq j, h_i = h_j$ が成り立つまで選ぶとき、必要なサンプル数 $n$ の期待値は $O(\sqrt{N})$ である。
ワーストケースは $H$ が一様分布の場合で、その場合の期待値はおおよそ $1.25\sqrt{N}$ であることが知られています。
解法
$N = 10^{10}$ として、区間 $[0,1) \subset \R$ を $N$ 等分しておきます。つまり、$I_k = [k/N, (k+1)/N)$ として $[0,1)$ を $I_0, I_1, \ldots, I_{N-1}$ に分割します。
探索空間内の $(a, b, c)$ に対して、$ax^3+bx^2+cx$ の小数部分は唯一の $I_k$ に含まれます。そのような $k$ を $H(a,b,c)$ と書きます。
探索空間内の $(a,b,c)$ を一様ランダムに選ぶと、$H$ は $\{0,1,\ldots,N-1\}$ に値を持つ確率変数となります。したがって、期待値 $O(\sqrt{N})$ 回のサンプリングの結果、$H(a_1,b_1,c_1) = H(a_2,b_2,c_2)$ を満たすサンプル $(a_1,b_1,c_1)$, $(a_2, b_2, c_2)$ が得られます。
特に、ある $k$ に対して$(a_1x^3 + b_1x^2 + c_1x)$ の小数部分と $(a_2x^3 + b_2x^2 + c_2x)$ の小数部分は同じ $I_k$ に属します。
そこで、$a = a_1 – a_2, b = b_1 – b_2, c = c_1 – c_2$ とすれば、ある整数 $d$ が存在して $|ax^3+bx^2+cx+d| < 1/N$ が成り立つことが分かります。
これらが成り立っても、$(a_1,b_1,c_1) = (a_2,b_2,c_2)$ となっていることが考えられますが、探索空間を十分大きくとっておけば、この確率は例えば $H$ の衝突確率の $1/2$ 倍以下にできて、衝突検知に十分な回数成功するまでに解 $(a,b,c,d)\neq (0,0,0,0)$ が得られることが期待できます。
この解法の期待計算量は、許容誤差 $\varepsilon$ に対して $O(\varepsilon^{-1/2})$ (as $\varepsilon \to 0$) で、本問の制約 $\varepsilon = 10^{-10}$ において AC を得ることができます。
実際には、計算誤差が難敵です。目標誤差を $0.5\cdot 10^{-10}$ にする（したがって $N = 2\cdot 10^{10}$ ととる）などしました。小数第 $10$ 位付近が 64 bit 浮動小数点数の有効数字では消えてしまう可能性も大きく、係数 $a, b, c$ を小さくして $f(a, b, c)$ が大きくならないようにするなどの試行錯誤を少しして、適当な回数の提出を行うことで AC となりました。この辺の詰めはだいぶ怪しいと思います。
ところで、本問の制約「絶対値が $10^4$ 以下で誤差 $10^{-12}$ 以下の $(a,b,c)$ の存在」も今回取り上げた解法から、任意の $x\in \R$ に対して必ず満たされることが分かります。$a, b, c\in [0, 10^4]$ に対して $ax^3 + bx^2 + cx$ の小数部分を考え、小数点第 $12$ 位までが完全に等しくなる $2$ パターン（鳩ノ巣原理より存在）の差をとれば証明できます。
