切り下げ?切り上げ?オーバーフローを避ける不等号の演算(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」を足してから計算すると便利。

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

$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 $