PCロール

PCロール

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

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

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

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

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

ABC176 A 問題

結論

A ÷ B を切り上げた値は

⌊a+b−1b⌋\left\lfloor \frac{a+b-1}{b} \right\rfloor

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

プログラム例

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

code
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

となるので、

code
python
編集モード
if (n % x == 0)
    count = n // x
else
    count = n // x + 1

と書くこともできます。

証明

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

⌈ab⌉=⌊a+b−1b⌋\begin{equation} \left\lceil \frac{a}{b} \right\rceil = \left\lfloor \frac{a+b-1}{b} \right\rfloor \end{equation}

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

  1. a=bka=bk (k=1,2,3,…k=1,2,3,\ldots) のとき、
⌈ab⌉=⌈bkb⌉=⌈k⌉=k⌊a+b−1b⌋=⌊bk+b−1b⌋=⌊k+b−1b⌋=k(∵0≤b−1<b)\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+la=bk+l (l=1,2,…,b−1l=1,2,\ldots,b-1) のとき，
⌈ab⌉=⌈bk+lb⌉=⌈k+lb⌉=k+1(∵0<l<b)⌊a+b−1b⌋=⌊bk+l+b−1b⌋=⌊k+1+l−1b⌋=k+1(∵0≤l−1<b)\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