D - 2-variable Function

[hxrxchang]

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

問題概要

整数Nが与えられる。 非負整数(a, b) の組で a ** 3 + a ** 2 * b + a * b ** 2 + b ** 3 が N以上になる最小のXを求めよ。 制約は 0 <= N < 10 ** 18

解き方

N が 10 18 と糞でかいが、`a 3 + a 2 b + a b 2 + b 3の中に、a 3,b 3があることから、非負整数の組み合わせa, bは最大10 6まで見ればいいことが分かる。 a, bの組み合わせを求めるには、aを全探索で決め、bは2分探索で求めると10 * 6 log2(10 6)で探索できる。 二分探索できる理由は、bが大きくなるにつれてXも大きくなる(単調増加する)から。 0, 1, 2, ..., 10 6 + 1` の配列に対して、

• ng: Xがn未満になる
• ok: Xがn以上になる の境界を求めて、okの最小値をbとすると最小のXを求められる。

func solve() {
    n := getInt()

    b := rangeSlice(pow(10, 6) + 2)

    ans := BIGGEST
    for a := 0; a < pow(10, 6) + 1; a++ {
        // ng: calc(a, b)がn未満
        // ok: calc(a, b)がn以上
        ng, ok := -1, pow(10, 6) + 2
        for ok - ng > 1 {
            mid := (ok + ng) / 2
            if calc(a, b[mid]) >= n {
                ok = mid
            } else {
                ng = mid
            }
        }
        ans = min(ans, calc(a, b[ok]))
    }

    fmt.Println(ans)
}

func calc(a, b int) int {
    return a * a * a + a * a * b + a * b * b + b * b * b
}

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