PCロール

PCロール

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

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

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

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

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

ABC176 A 問題

結論

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} $$

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

  1. $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} $$

  1. $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} $$

おわりに

最後までご覧いただきありがとうございます。 PC ロールでは、テクノロジーに関する情報をまとめて

発信しています。 また、おすすめのガジェットについて幅広く紹介していく、ガジェロールもあります。 ガジェットやソフトを使うエンジニア・クリエイターはぜひご覧ください。

← Back to home