切り下げ?切り上げ?オーバーフローを避ける不等号の演算(c++)

atcoderの整数の掛け算で、オーバーフローを避けるため、代わりに割り算を使用する事がある。

不等号がついている式で演算を行う際に、小数点を切り捨てか、切り上げかわからなくなったのでメモ。

問題
不正解の例
正解の例
本当にこれでいいの？
覚え方

問題

$a \times b$ が $N$ より大きければ true を出力し、そうでなければ false を出力せよ。

ただし $ 1 \leq a, b, N \leq 10^{18} $ とする

不正解の例

$a * b$が、long long の最大値($9 \times 10^{18}$)を超えてしまうため、オーバーフローが発生し、正しく計算ができない。

if(a * b > N){
  cout << "true" << endl;
}else{
  cout << "false" << endl;
}

正解の例

掛け算ではなく割り算を使うことで、オーバーフローを回避できる。

if(a > N / b){
  cout << "true" << endl;
}else{
  cout << "false" << endl;
}

本当にこれでいいの？

c++では整数型の割り算を実行したときに、自動的に小数点の切り下げが発生する。
例えば10/3の場合、この実行結果は$3.333333….$ではなく、$3$になるため、不等号の計算で少し不安になる。

場合によっては切り上げにする必要があるので注意する。

また、切り上げするときには、(N + b - 1) / bのように、分子に「分母-1」を足してから計算すると便利。

書き換え前	書き換え後	c++での表記
$a * b < N$	$a < \lceil \frac{N}{b} \rceil $	$a < (N + b – 1) / b$
$a * b \leq N$	$a \leq \lfloor \frac{N}{b} \rfloor$	$a <= N / b$
$a * b > N$	$a > \lfloor \frac{N}{b} \rfloor$	$a > N / b$
$a * b \geq N$	$a \geq \lceil \frac{N}{b} \rceil $	$a >= (N + b – 1) / b$

具体的な数字を当てはめて計算してみるのがいいと思う。

$a<\frac{N}{b}$を考える。 aを5.0とすると、$\frac{N}{b}$は5.1以上じゃないといけない
$\frac{N}{b}$が5.1の時(不等号は成り立つ)、$\lfloor \frac{N}{b} \rfloor$は5.0になる(不等号は成り立たない)
$\frac{N}{b}$が4.9の時(不等号は成り立たない)、$\lfloor \frac{N}{b} \rfloor$は4.0になる(不等号はなりたたない)。
(2)が矛盾しているので切り上げる必要がある。

覚え方

除算の部分は, 以下のように表すことができる。

$$ \lfloor \frac{N}{b} \rfloor \leq \frac{N}{b} \leq \lceil \frac{N}{b} \rceil $$

$$ \lceil \frac{N}{b} \rceil \geq \frac{N}{b} \geq \lfloor \frac{N}{b} \rfloor $$

「=」がつかない不等号($<, >$)はできるだけ遠くの値になる丸め方を選ぶ。

「=」がつく不等号($\leq, \geq$)はできるだけ近くの値になる丸め方を選ぶ。

$a * b < N$ のときは $ \lceil \frac{N}{b} \rceil $
$a * b \leq N$ のときは $ \lfloor \frac{N}{B} \rfloor $
$a * b > N$ のときは $ \lfloor \frac{N}{B} \rfloor $
$a * b \geq N$ のときは $ \lceil \frac{N}{b} \rceil $

書き換え前	書き換え後	c++での表記
\(a * b < N\)	\(a < \lceil \frac{N}{b} \rceil \)	\(a < (N + b – 1) / b\)
\(a * b \leq N\)	\(a \leq \lfloor \frac{N}{b} \rfloor\)	\(a <= N / b\)
\(a * b > N\)	\(a > \lfloor \frac{N}{b} \rfloor\)	\(a > N / b\)
\(a * b \geq N\)	\(a \geq \lceil \frac{N}{b} \rceil \)	\(a >= (N + b – 1) / b\)