ABC339-F Product Equality の確率を保証する

$\lbrack 10 ^ 9 , 2 \times 10 ^ 9 \rbrack$ から一様ランダムに素数 $P$ を選ぶ *1 。 $A _ i A _ j \neq A _ k$ となる $1$ 組の $( i , j , k )$ を固定し、誤判定する、すなわち $A _ i A _ j \equiv A _ k \pmod P$ となる確率を求める。これは $A _ i A _ j - A _ k$ が $P$ で割り切れることと同値である。

$\lbrack 10 ^ 9 , 2 \times 10 ^ 9 \rbrack$ の範囲に素数は $47374753$ 個存在する *2 。一方、 $0 \lt \lvert A _ i A _ j - A _ k \rvert \leq 10 ^ { 2000 }$ であるから、 $A _ i A _ j - A _ k$ は範囲内の素因数を $222$ 個以下しか持たない。よって一様ランダムに選んだとき、誤判定の確率は $222 / 47374753 \leq 10 ^ { - 5 }$ 以下である。

$4$ つの素数を一様ランダムかつ独立に選ぶと、全ての素数で同時に誤判定する確率は $\left ( 10 ^ { - 5 } \right ) ^ 4 = 10 ^ { - 20 }$ 以下である。独立に選ぶ部分が重要で、独立な事象が同時に発生する確率はその積となるという性質を用いて確率を抑えている。

$1$ つのケースで最大 $N ^ 3 \leq 10 ^ 9$ 組の $( i , j , k )$ に対して判定を行うので、 $1$ 回以上誤判定する確率は $10 ^ { - 20 } \times 10 ^ 9 = 10 ^ { - 11 }$ 以下である。この部分は union bound ( Boole's inequality - Wikipedia ) と呼ばれる直感的にはほとんど明らかな不等式を用いた。この $N ^ 3$ 組では同じ $P$ を使っているため、これらの事象は独立ではない。よって $1 - \left ( 1 - 10 ^ { - 20 } \right ) ^ {10 ^ 9}$ と計算するのは誤りである。

テストケース間では $P$ を取り直すのでそれぞれは独立となるが、独立性を気にせず union bound を使った方が簡単になる。全体で $1000$ ケースある場合、 $1$ ケース以上 WA となる確率は $10 ^ { - 11} \times 1000 = 10 ^ {- 8}$ 以下である。 $1000$ ケースという想定が甘いかどうかと、 $10 ^ {- 8 }$ という確率が許容可能かどうかは各自で判断するしかない。人生が終わるまでにジャッジできる量、宇宙線でアルゴリズムが破損するより低い確率、などで無理やり上限を付けることはできるかもしれない。