AtCoder ABC330 B,C 最小値問題 解説補足

B - Minimize Abs 1

B - Minimize Abs 1

以下の数式において、 a と x の範囲 [l, r] が与えられる時、解が最小値となる x を求めよ。

$$
|x - a| \quad(l \le x \le r)
$$

解説

y = |x-a| とすると、グラフは以下のようになる。

従って a の位置がどこにあるかで、最小値が決まる。

(i) l <= a <= r ならば、最小値は x = a の時

(ii) a < l ならば、最小値は x = l の時

(iii) r < a ならば、最小値は x = r の時

C - Minimize Abs2

C - Minimize Abs 2

以下の数式において、Dが与えられた時、その最小値を求めよ。

$$
|x^2 + y^2 - D|
$$

制約

• x, y は非負整数

• 1 ≤ D ≤ $${2 \times 10^{12}}$$

解説

変数xの範囲を定める。
題意「 $${|x^2 + y^2 - D|}$$ の最小値を求める」より、
xの範囲は、 $${0 \le x \le \sqrt{D}}$$ と定まる。
⇒ $${x^2 = D + \alpha}$$ とおくと、 $${|y^2 + \alpha|}$$ となり、この最小値は、 $${\alpha = 0}$$ のときである。
したがって $${x^2}$$ の範囲は、対称性から $${0 \le x^2 \le D}$$　で良い。

x が定まるので、$${c = x^2 - D}$$ とおくとことで、固定値cを定義できる。
問題は、 $${|y^2 + c|}$$ の最小値を求める 問題となる。

この時、
1. c ≥ 0 の時、$${|y^2 + c|}$$ の最小値は |c| (y = 0) が定まる。

2. c < 0 の時、
$${|y^2 + c|}$$ の最小値は、 yの値が整数で有ることを考慮して、 $${\sqrt{-c}}$$ に近い方の値が最小値となる。
最小値 = min($${ \sqrt{ \lfloor -c \rfloor}}$$,  $${ \sqrt{ \lceil -c \rceil }}$$)