夏休みの思い出（１） [yukicoder No.550] - はまやんはまやんはまやん

解説放送

解法

https://yukicoder.me/submissions/192940

二分探索で解く。

まず、極値のx座標を求める。
f(x) = x^3 + Ax^2 + Bx + C
f'(x) = 3x^2 + 2Ax + B
f'(x) = 0を見たすxは x = (-A ± sqrt(A^2 - 3B)) / 3 である。
極値のx座標を小さい方から、x=D, x=Eとすると、この三次関数は、(-INF,D), [D, E], (E,INF)の3つの間で単調性を持つ。
なので、この3つの区間に対して二分探索をして、=0となる点を見つける。

関数の計算は10^18を越えるので、多倍長整数を利用する。
C++14(gcc 7.1.0)では__int128_tが使えるので、これを使うと正確に計算ができる。

typedef long long ll;
#define EPS 0
ll A, B, C;
double a, b, c;
__int128_t aa, bb, cc;
//---------------------------------------------------------------------------------------------------
__int128_t f(__int128_t x) { return x*x*x + aa*x*x + bb*x + cc; }
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B >> C;

    a = A, b = B, c = C;
    aa = A, bb = B, cc = C;
    double d = (-a - sqrt(a *a - 3 * b)) / 3;
    double e = (-a + sqrt(a *a - 3 * b)) / 3;

    ll low, high;

    low = -1010101010LL, high = floor(d);
    while (low + 1 != high) {
        ll x = (low + high) / 2;
        if (0 <= f(x)) high = x;
        else low = x;
    }
    printf("%lld ", high);

    high = ceil(d), low = ceil(e);
    if (high != low) {
        while (high + 1 != low) {
            ll x = (low + high) / 2;
            if (0 <= f(x)) high = x;
            else low = x;
        }
    }
    printf("%lld ", high);

    low = floor(e), high = 1010101010LL;
    while (low + 1 != high) {
        ll x = (low + high) / 2;
        if (0 <= f(x)) high = x;
        else low = x;
    }
    printf("%lld\n", high);
}