【競プロ】余りを切り上げる

この記事は、Gajeroll Advent Calendar 2022 の 13 日目の記事です。

はじめに
結論
プログラム例
証明
おわりに

はじめに

今回の記事は，競技プログラミングでも定番の、割り算において余りを切り上げる処理についてです。

例えば、以下の ABC176 A 問題では $N$ 個のたこ焼きを $X$ 個ずつ作るときに、何回作る必要があるのかを求めます。

A - Takoyaki

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

結論

A ÷ B を切り上げた値は

$$
\left\lfloor \frac{a+b-1}{b} \right\rfloor
$$

と表現することができます。

プログラム例

先ほどの ABC176 A 問題の Python での回答例は以下のようになります。

n, x, t = map(int, input().split())
count = (n + x - 1) // x  # n ÷ x で余りを切り上げた値
res = count * t
print(res)

また、count を求める部分は、

n が x で割り切れる場合には、n ÷ x
n が x で割り切れない場合には、n ÷ x + 1

となるので、

if (n % x == 0)
    count = n // x
else
    count = n // x + 1

と書くこともできます。

証明

任意の正の整数 $a, b$ に対して、

$$
\begin{equation}
\left\lceil \frac{a}{b} \right\rceil = \left\lfloor \frac{a+b-1}{b} \right\rfloor
\end{equation}
$$

が成り立つことを証明する。

$a=bk$ ($k=1,2,3,\ldots$) のとき、

$$
\begin{gather}
\left\lceil \frac{a}{b} \right\rceil = \left\lceil \frac{bk}{b} \right\rceil = \left\lceil k \right\rceil = k \\
\left\lfloor \frac{a+b-1}{b} \right\rfloor = \left\lfloor \frac{bk+b-1}{b} \right\rfloor = \left\lfloor k+\frac{b-1}{b} \right\rfloor = k \quad(\because 0 \leq b-1< b)
\end{gather}
$$

$a=bk+l$ ($l=1,2,\ldots,b-1$) のとき，

$$
\begin{gather}
\left\lceil \frac{a}{b} \right\rceil = \left\lceil \frac{bk+l}{b} \right\rceil = \left\lceil k+\frac{l}{b} \right\rceil = k+1 \quad(\because 0<l<b) \\
\left\lfloor \frac{a+b-1}{b} \right\rfloor = \left\lfloor \frac{bk+l+b-1}{b} \right\rfloor = \left\lfloor k+1+\frac{l-1}{b} \right\rfloor = k+1 \quad(\because 0\leq l-1<b)
\end{gather}
$$