2-variable Function [AtCoder Beginner Contest 246 D]

https://atcoder.jp/contests/abc246/tasks/abc246_d

前提知識

• 二分探索

解説

https://atcoder.jp/contests/abc246/submissions/30680524

なかなか難しいというか、競プロ的なアプローチを含んだ問題。
二分探索が分かっていない場合はそちらを先に学習してきてほしい。

何から始めるのか

サンプルを自力でうまく解くような方法が無いかを探してみる。
入力1に対して答えを見つけようとした場合、Xの候補である9, 10, 11, ...が条件を満たすかどうかを
判定して、満たす最小のものを答える方法が考えられる。
しかし、とあるXに対して、そのXが条件を満たすかどうかを判定するのはやや難しく、
別のアプローチが無いかを考えてみることにする。

候補が全列挙できるのでは？

ここから競技プログラミングで良く出てくる候補の全列挙をベースに考えてみる。
とあるXが条件を満たすかを判定するのは難しいので、生成の元となっているa,bの列挙から攻めてみる。
3乗が含まれるので、a,bはそれぞれ10⁶が上限であることが分かる。
aは非負整数、かつ、少なくとも a³ ≦ 10¹⁸ なので、 a ≦ 10⁶ である必要があるということ。

これでa,bの全列挙が出来れば、条件を満たすXをすべて生成できるので、ここからX以上の最小値を求めればいい。
だが、このままやるとTLE

片方を効率化する

aは[0, 10⁶]の範囲で全探索するとして、bをもっと賢く探索できないかを考えてみる。
条件となっている多項式の計算をf(a,b)と置いて考えてみる。
とあるaについて、
f(a,0), f(a,1), f(a, 2), ...
というのを考えてみると、とある部分を境目としてN以上になっているはずである。
この「とある部分を境目として」という部分から二分探索が使えそうと思い立てば、もう解法は目の前である。

二分探索

bは[0,10⁶]のどこかに最適解が存在するが、N≦f(a,b)を満たすかというのを条件にして境目を見つけよう。
境目が見つかれば、その境界線上のbの大きいほうの値が最適なbになっているはずなのでf(a,b)について
答えの候補として更新していこう。

ll N;

ll f(ll a, ll b) {
    return a * a * a + a * a * b + a * b * b + b * b * b;
}

void _main() {
    cin >> N;

    ll ans = infl;
    rep(a, 0, 1010101) {
        ll ng = -1, ok = 1010101;
        while (ng + 1 != ok) {
            ll md = (ng + ok) / 2;
            if (N <= f(a, md)) ok = md;
            else ng = md;
        }
        chmin(ans, f(a, ok));
    }
    cout << ans << endl;
}