ABC246D - 2-variable Function

考え方

式変形（因数分解など）で何かを見出そうとしても上手く行かない．

2変数の問題は，

• 2次元平面で考える
• 1変数を固定して考える

とよい．

---

$0 \leq N \leq 10^{18}$だから，$0 \leq a,b \leq 10^{6}$である．よって，$a,b$の全探索はできない．

$f(a,b) = a^{3} + a^{2}b + ab^{2} + b^{3} = (\text{定数}) = X$は，2次元平面上の1つの曲線を与える．今回は，$X \geq N$をなるべく$N$に近くとりつつ，非負整数の格子点$(a, b)$を通る曲線を探したい．

$a$を固定できたとして，$b_{a} = \min \{b \mid f(a,b) \geq N \}$を求める方法を考える．

まず，$f(a,b)$は$b$の単調増加関数だから，二分探索（$O(\log (10^{6}))$）が使える．$a$を全探索しても$O(10^{6} \log (10^{6}))$で間に合う．

あるいは，$b_{a}$が$a$に関する単調減少関数であることに気づくと，$a$を$+1$するたびに$b_{a}$は減るか変わらないかだから，二分探索を使わずに解ける（$O(10^{6})$）．
Editorial - AtCoder Beginner Contest 246

回答例

【二分探索】

N = int(input())

ans = N ** 3
for a in range(10 ** 6 + 1):
    ok = 10 ** 6
    ng = -1
    while ok - ng > 1:
        mid = (ok + ng) // 2
        x = a ** 3 + (a ** 2) * mid + a * (mid ** 2) + mid ** 3
        if x >= N:
            ok = mid
        else:
            ng = mid
    x = a ** 3 + (a ** 2) * ok + a * (ok ** 2) + ok ** 3
    ans = min(ans, x)

print(ans)

【探索の工夫】

N = int(input())

def f(a, b):
    return a ** 3 + (a ** 2) * b + a * (b ** 2) + b ** 3

ans = N ** 3
b = 10 ** 6
for a in range(10 ** 6 + 1):
    while b > 0 and f(a, b) >= N:
        b -= 1
    if f(a, b) < N:
        b += 1
        ans = min(ans, f(a, b))

print(ans)

$a$を増やしたのに$b$が変わらなければ，答えとしてほしい最小値を更新することはない．つまり，$a$が増えれば，必ず$b$は1以上小さくなるから，以下でも良い．

N = int(input())

def f(a, b):
    return a ** 3 + (a ** 2) * b + a * (b ** 2) + b ** 3

ans = N ** 3
b = 10 ** 6
for a in range(10 ** 6 + 1):
    while b > 0 and f(a, b) >= N:
        ans = min(ans, f(a, b))
        b -= 1

print(ans)

$f(a,b)$は$a, b$に対して対称な式だから，$a \leq b$の範囲だけを探索すればよい．「しゃくとり法」の形で実装できる．

N = int(input())

def f(a, b):
    return a ** 3 + (a ** 2) * b + a * (b ** 2) + b ** 3

ans = N ** 3
a = 0
b = 10 ** 6
while a <= b:
    if f(a, b) >= N:
        ans = min(ans, f(a, b))
        b -= 1
    else:
        a += 1

print(ans)