競技プログラミングで、整数a,bからなるa/bの切り上げが(a+b-1)/bの切り捨てに等しい理由をやっと理解したので、忘れないように記事にします。
例えば、下記の等式を考えます。
2/3 = (2+3-1)/3 = 1.333... → 1
3/3 = (3+3-1)/3 = 1.666... → 1
5/3 = (5+3-1)/3 = 2.333... → 2
6/3 = (6+3-1)/3 = 2.666... → 2
//ここでは"→"は切り捨てを意味します。
上記の等式からa/bの切り上げが(a+b-1)/bの切り捨てになることが分かります。 それでは、これからそうなる説明を行います。
まず、(a+b-1)/bの分解を行います。
(a+b-1)/b = a/b + (b-1)/b ...①
ここで(b-1)/bはあと1/bを加えれば1になる数です。 a/bが割り切れない場合は下記になります。
a/b = xb/b + (a-bx)/b ... ②
//xは正の整数
上記②式の右辺第1項にbで割り切れる数、第2項にそのあまりを置いています。 整数a,bは整数ですので、a - bxは1以上になり、(a-bx)/bは1/b以上です。 ※a/bが割り切れる場合は第2項が0になります。
①式に②式を代入すると下記になります。
(a+b-1)/b = xb/b + (a-bx)/b + (b-1)/b ... ③
//a/bが割り切れない場合、(a-bx)/bが1/b以上なので
(a-bx)/b + (b-1)/b ≥ 1 ... ④
a/bが割り切れない場合、(a-bx)/bが1/b以上なので上記③式から上記④式が求められます。 そのためa/bが割り切れない場合、①式の(a+b-1)/bの一の位はa/b一の位に1を加えた数になります。
したがって、a/bの切り上げが(a+b-1)/bの切り捨て((a+b-1)/bの小数点以下を捨てた数)に等しくなります。