after_contestケースが追加され、吸収できるかどうかの判定を倍精度浮動小数点数型(c++ならdouble、pythonならfloat、rustならf64、etc)で行う解法がWAになるようになりました。

if (吸収したいスライムの大きさ) < (高橋君の大きさ)/X:
    吸収する

具体的には、以下のとき、浮動小数点数の丸め誤差の影響により判定に失敗します。

• \(X=2^{14}=16384\)
• 吸収したいスライムの大きさが \(2^{39}=549755813888\)
• 高橋君の大きさが \(2^{53}+1=9007199254740993\)

どうすればよいか

案1

\(X\) を移項し、

slime_size * X < takahashi_size

とすることで整数演算で判定することができます。ただし、左辺は \(2^{64}\) 以上の値を取りうるため、オーバーフローに注意する必要があります。(128bit整数や多倍長整数を使うほか、一旦doubleで乗算を計算して \(2^{60}\) 程度以上かどうかで場合分けするなどの方法があります）

案2

• \(n\) を整数、\(\alpha\) を実数とするとき、\(n < \alpha \Longleftrightarrow n < \lceil\alpha\rceil\) が成り立つ
• \(a\) を整数、\(b\) を正整数とするとき、 \(\displaystyle \left\lceil\frac{a}{b}\right\rceil =\left\lfloor\frac{a+b-1}{b}\right\rfloor\) が成り立つ

この2つの性質を使うことで、

slime_size < (takahashi_size + X-1) / X

のように整数演算で不等式部分の計算を行うことができます。(整数除算は切り捨てになると暗黙的に仮定しています)

公式解説のコードもこのように書かれています(37行目)