(a + b - 1) / b で a / b の切り上げを計算する

整数 a, b に対して、 a / b の切り上げを計算したい場合 (a + b - 1) / b するという小技が競技プログラミングではよく使われる。 なぜこれで切り上げが計算できるのか、良い感じの説明が検索しても出てこなかったので自分なりの理解を書いておく。

以下 / は一時的に分数の記号として、 b = 3 , a を 3から1ずつ増加させていく場合を考える。

3/3 = 1

4/3 = 1+1/3

5/3 = 1+2/3

6/3 = 2

7/3 = 2 + 1/3

...以下略

となるので、1 - 1 / b （b=3 の場合は 2/3) を加算して小数点以下を切り捨てれば切り上げと同じになる。

切り上げすべき場合は必ず商が繰り上がる。

切り上げすべきでない場合（上記の 3/3 , 6/3 のケース）は商が繰り上がらない。

よって、floor(a/b + (1-1/b))をすればよく、今度は / を切り捨て除算の記号として式変形すると (a+b-1)/b で同値と言える。したがってa / b の切り上げを計算したい場合 (a + b - 1) / b で計算できる。

ceil が使える言語ならそれでもいいんじゃないか？と思われるが、a, b の値によっては浮動小数点計算の誤差が発生する可能性があるので、この方法が安全らしい。なるほど。

まあ (a+b-1)/b の方がシンプルだし賢いやり方感がある。