初めに
公式と若干説明が違いそうなので書いておく。 趣旨としてはよくわかんなったらエクセル使って視覚的にみてみるのもいいよ、ということで。
あまり数学的な整理はしないので、正確な理解は別の説明に譲る。
解説的に色弱の方にはわかりづらい内容かもしれないのでそこは申し訳ないです。（グレースケールで描いたらなんか錯視的に直観とずれたので、色付きのままです。）
問題
当時の分析
因数分解し始めて時間を食ったのち、とりあえずエクセルで横軸a,縦軸bで実際に描写して値がどう変化するかを観察してみる。
これを眺めながら、
- Nとして特定の色を指定されて、どれだけ近い色を見つけられるか、という問題ともいえる。
- 色の変化は左上を中心とした同心円状に変化しているように見える。
という訳で、例えば薄めのオレンジ色を探す問題せっていなら、なんとなく下記図の3角形にありそう。だし、視覚的にも薄めのオレンジは三角の中に入ってそう。
従い、まず対角線で該当色近辺の色が出始める場所を探し、そのあと右にずらしながら該当色に近いものを探してく。
- 言い換えると、a==bとして、N<f(a,a)となるaを探す。
- aを増やしつつ、b=[0,a]の範囲でNになるべく近くなるbを探して、よりベターなら更新する。
条件的にa^3<=10^18で、10^6の規模でできそう。
私の場合は2分探索で実装したが、前述の3角形の範囲にありそう=f(i,j)<f(i+1,i-1)なことを考えれば尺取りっぽくも行けそう。
コード
N = int(input())
def calc(a, b):
return a**3 + a**2 * b + a * b**2 + b**3
#1 対角線操作
for ab in range(10**6 + 1):
if N <= 4 * ab**3:
break
#2 同色探索
ret = 4 * ab**3
for a in range(ab, 2 * ab + 1):
l = -1
r = a + 1
m = (l + r) // 2
while l < m:
t = calc(a, m)
if t < N:
l = m
else:
r = m
m = (l + r) // 2
ret = min(ret, calc(a, r))
if m == -1:
break
print(ret)
2022/4/4追記
公式に貼ってある解説を眺めながらそもそもあんまり意味がないことしているよね、というのに気付いたので追記する。
改めて考察
別に対角線を探索する行為(①）は不要で、最初から②だけやっておいても計算量的には十分間に合う。
下記みたいな感じ。
別解検討
エクセル図再訪
せっかくなので2枚目の図の3角形を活用したい。眺めていると薄いオレンジ色は右上方向に存在していることがわかる。
とすると、bの全範囲を二分探索で探す必要はなくて、aを増やす→N<f()になるまでbを減らす→...を繰り返していけばいい。以下みたいな感じ。
計算量について考えてみると、
b^3<=a^3 b<=a<10^6
を踏まえ、二分探索をする対角線走査の有無にかかわらずO(aloga)になる。一方で、新解法だとO(a)で済む。
コード
N = int(input())
def calc(a, b):
return a**3 + a**2 * b + a * b**2 + b**3
ret = 0
for a in range(10**6 + 1):
ret = calc(a, a)
if N <= ret:
break
b = a
while a <= 10**6 + 1:
while b >= 0:
r = calc(a, b)
if N <= r:
ret = min(ret, r)
else:
break
b -= 1
a += 1
print(ret)