切り下げ?切り上げ?オーバーフローを避ける不等号の演算(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\)

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

  1. \(a<\frac{N}{b}\)を考える。 aを5.0とすると、\(\frac{N}{b}\)は5.1以上じゃないといけない
  2. \(\frac{N}{b}\)が5.1の時(不等号は成り立つ)、\(\lfloor \frac{N}{b} \rfloor\)は5.0になる(不等号は成り立たない)
  3. \(\frac{N}{b}\)が4.9の時(不等号は成り立たない)、\(\lfloor \frac{N}{b} \rfloor\)は4.0になる(不等号はなりたたない)
  4. (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 \)

コメント

タイトルとURLをコピーしました