2022-10-14

ABC236 E - Average and Median

二分探索

Tips. 平均値や中央値の最大化には二分探索が有効

平均値としてあり得る値の最大値

入力例1のとき、次の図のように考えられる。
max_sum は B の隣り合う値の少なくとも一方を選択したときの、選択した値の和とする。
max_sum は簡単なdpを行うことで求められる。
平均値としてあり得る値の最大値は近似値を求めればよいので、 $r - l \le 10^{-6}$ となるまで二分探索を行う。

中央値としてあり得る値の最大値

入力例2のとき、次の図のように考えられる。
B を下図のように定義することで、平均値のときと同様にして求めることができる。

提出コード

2022-10-11

ARC150 B - Make Divisible

平方分割

問題へのリンク

まず、 $B \lt A$ のときは $X=0, Y=A-B$ のときに $X+Y$ が最小となる。

以下では $B \ge A$ のときについて考える。

$X+Y$

$\frac{B+Y}{A+X} = k \space ( k \ge 1)$ とする。

このとき式変形すると、 $X+Y = (k+1)X + kA - B$ となる。
$k$ が固定されているとき、 $X = \frac{B+Y}{k} - A$ であるから、 $X = max( \lceil \frac{B}{k} \rceil - A, 0 )$ がとりうる最小の $X$ となる。

また、 $\lceil \frac{B}{k} \rceil = \lfloor \frac{B-1}{k} \rfloor + 1$ であることから、

$X+Y = (k+1)max( \lfloor \frac{B-1}{k} \rfloor + 1 - A, 0 ) + kA - B$ を最小化すればよい。

平方分割

$\lfloor \frac{B-1}{k} \rfloor$ が同じものについては $k$ が小さいほうが $X+Y$ が小さくなる。

よって、 $\lfloor \frac{B-1}{k} \rfloor$ の取りうるすべての値について $X+Y$ の値を求めて、最小値を得る。

$i) \space k \le \lceil \sqrt{B-1} \rceil$ のとき
$\lceil \sqrt{B-1} \rceil$ 通りについて、 $X+Y$ を求める。

$ii) \space k \gt \lceil \sqrt{B-1} \rceil$
このとき、 $\lfloor \frac{B-1}{k} \rfloor \le \lceil \sqrt{B-1} \rceil$ であるから、 $\lfloor \frac{B-1}{k} \rfloor$ のとりうる値は高々 $\lceil \sqrt{B-1} \rceil$ 通りである。
したがって、 $Q = 0, ... , \lceil \sqrt{B-1} \rceil$ について、 $\lfloor \frac{B-1}{k} \rfloor = Q$ となる最小の $k$ を求めることで、 $X+Y$ を求めることができる。