小数点以下を切り上げる場合の商を求める方法【競技プログラミング】

有名な内容だと思うが、自分用にメモ

整数型同士の割り算は切り捨てられる。

$a$, $b$を整数型($a$, $b>0$)とするとき, $a/b$を計算すると小数点以下は切り捨てられる。
例)
(i) $a=4, b=2$
$4/2=2$
整数型同士の計算の場合は小数点以下は切り捨てられ、2となる。

(ii) $a=5, b=2$
$5/2=2.5$
整数型同士の計算の場合は小数点以下は切り捨てられ、2となる。

通常、整数型同士の割り算は切り捨てられ、そのままだと切り上げることはできない。

切り上げるためにはどうするか？

\frac{a+b-1}{b}

を計算し、小数点以下を切り下げると、$a/b$の小数点以下を切り上げた結果が得られる。
$a=4, b=2$
$(4+2-1)/2=5/2=2.5$
の小数点以下を切り捨てると、$2$となる。
確かに$4/2=2$で小数点以下を切り上げると$2$だから合ってる。

$a=5,b=2$
$(5+2-1)/2=6/2=3$
の小数点以下を切り捨てると、$3$となる。
両方とも$a/b$の小数点以下を切り上げた結果になっている。

証明

$[]$をガウス記号とする。(ここでは、小数点以下を切り捨てる程度の意味)
$a$が$b$で割り切れるか割り切れないかで場合分けする。

(i) $a$が$b$で割り切れる
$a=bk$とおける($k$は整数)。この時,

\left[\frac{a+b-1}{b}\right]=\left[\frac{bk+b-1}{b}\right]=\left[k+\left(1-\frac{1}{b}\right)\right]=k

$a/b=k$の小数点以下を切り上げても$k$であるから、確かに合っている。

(ii) $a$が$b$で割り切れない
$a$を$b$で割った時の余りを$l$と置くと, $a=bk+l$とおける($k,l$は整数, ただし, $1\le l<b$)。この時,

\left[\frac{a+b-1}{b}\right]=
\left[\frac{bk+l+b-1}{b}\right]=\left[k+1+\left(\frac{l-1}{b}\right)\right]=k+1

$a/b=k+l/b$において$k$は整数部分で、$l/b$は小数部分であるから、小数点以下を切り上げると、確かに$k+1$となり結果は合っている。

実装

C++でプログラムを組み、確認した。

#include <iostream>

using namespace std;

int main(){
  int a, b;
  cin >> a >> b;

  cout << "a/b=" << a/b << endl;
  cout << "(a+b-1)/b=" << (a+b-1)/b << endl;
  return 0;
}

(i)$a=4$, $b=2$

$ ./a.out
4 2
a/b=2
(a+b-1)/b=2

(ii)$a=5$, $b=2$

$ ./a.out
5 2
a/b=2
(a+b-1)/b=3

結論

(a+b-1)/bを計算し、小数点以下を切り捨てると, a/bの小数点以下を切り上げた結果が得られる。