[AtCoder] D. 2-variable Function [Beginner Contest 246]

📚 質問する

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

📖 に答える

初めて問題を見た時、Nの最値と問題の内容を見て、バイナリ検索で接近したが、解決しなかった.
これは二重ポインタで解決した問題です.
nは大きいが、aおよびbの最値は10の18平方ではなく、10以下の6平方である.Nの最値は10の18平方であるため、Xが10の18平方である場合、aが10の6平方bが0である場合が可能である.そのため、最高価格は10の6平方です.
二重ポインタを利用するために,aとbのbをより大きな値に固定する.どうせaとbの値を変えるのは同じで、bがもっと大きいか等しい限りいいです.
a 0 bを10の6回にとり、投点を開始します.
aとbを問題とする演算 a ** 3 + a * a * b + a * b * b + b ** 3は、結果がn以上であれば1つのbが減少し、それ未満であればaが増加する.この過程を繰り返すと,aがbを超えると終了する.
n以上の場合、最小値に更新されます.

📒 コード#コード#

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


n = int(input())
s = 0
e = 10 ** 6

min_result = 100000000000000000000
while s <= e:
    result = f(s, e)
    if result >= n:
        min_result = min(min_result, result)
        e -= 1
    else:
        s += 1

print(min_result)

🔍 結果