Deadline - Educational Codeforces Round 80 div2 a

#math #ceil #不等式 #三分探索

解法

$x + \lceil \frac{d}{x + 1} \rceil \leq n$
$\lceil \frac{d}{x + 1} \rceil \leq n - x$
$\lceil \frac{d}{x + 1} \rceil (x + 1) \leq (n - x)(x + 1)$

$\lceil \frac{d}{x + 1} (x + 1) \rceil \leq \lceil \frac{d}{x + 1} \rceil (x + 1)$
∵
(左辺) = d
(右辺) = $\lceil \frac{d}{x + 1} \rceil + \lceil \frac{d}{x + 1} \rceil + ... + \lceil \frac{d}{x + 1} \rceil$
ここで, x ≤ $\lceil x \rceil$ < x + 1 より,
(右辺) ≥ $\frac{d}{x + 1} + \frac{d}{x + 1} + ... + \frac{d}{x + 1}$ = d

より,
$d \leq (n - x)(x + 1)$
-(n - x)(x + 1) + d ≤ 0
$x^2 - (n - 1)x + (d - n) ≤ 0 \ \ \ \ (1)$

f(x) = $x^2 - (n - 1)x + (d - n)$ とする
この関数の最小値が 0 以下になればいい

f ' (x) = 2x - (n - 1) = 0
x = $\frac{n - 1}{2}$

f( $\frac{n - 1}{2}$ ) ≤ 0 になるか

コード
https://codeforces.com/contest/1288/submission/68795164

別解 1

(1) から, 三分探索ができる

https://codeforces.com/contest/1288/submission/68888275

別解 2

editorial
https://codeforces.com/blog/entry/73105

x + $\lceil \frac{d}{x + 1} \rceil$ ≤ n
(左辺) = $\lceil x + \frac{d}{x + 1} \rceil$
∵
x $\in$ Z $_{\geq 0}$ , y $\in$ R $_{\geq 0}$ に対し,
x + $\lceil y \rceil$ = $\lceil x + y \rceil$
ceiling function は, 小数部を切り上げる
非負整数を足しても小数部は変わらない

f(x) = x + $\frac{d}{x + 1}$ とする
f ' (x) = 1 - $\frac{d}{(x + 1)^2}$ = 0
x + 1 = $\pm \sqrt{d}$
x ≥ 0 より, x + 1 > 0 であるから,
x + 1 = $\sqrt{d}$
x = $\sqrt{d}$ - 1

この x で f(x) (x ≥ 0) は最小値をとる
f(x) = x + $\frac{1}{x}$ を考えるとわかりやすい
y=x+1/xの最小値、グラフ、漸近線 - 具体例で学ぶ数学

$\lceil f(x = \sqrt{d} - 1) \rceil$ ≤ n
か確かめる

コード
https://codeforces.com/contest/1288/submission/68889079