「AtCoder Beginner Contest 345」のB問題を解いて、Pythonでの「切り上げ除算」の求め方を学んだので忘れないようにメモしておきます。
「AtCoder Beginner Contest 345」のB問題
問題内容は以下の通りで、簡単に言うと 『X/10の「切り上げ除算」を行ってください』 というものです。
$−10^{18}$以上$10^{18}$以下の整数X が与えられるので、$\lceil \frac{X}{10} \rceil$を出力してください。
ここで、$\lceil a \rceil$はa以上の整数のうち最小のものを意味します。
この問題をPythonで以下のように解いたのですが、
N = int(input())
if N%10 == 0:
ans = N//10
else:
ans = N//10 + 1
print(ans)
解説では$\lceil \frac{a}{b} \rceil = \lfloor \frac{a+b-1}{b} \rfloor$という計算式で簡潔に解けるよ、ということを教えてもらい勉強になったので、なぜこの計算式で解けるのかをメモがてら整理しておきます。
Pythonにおける除算演算子は「切り捨て除算」
Pythonの除算演算子//は「切り捨て除算」の結果を返します。
例えば、a=7、b=3のとき、a/b=2となる。
（a/b=2.333...の小数部が切り捨てられる）
また、「切り捨て」を行うロジックは下記2パターンあるようで、どちらのロジックで算出するかはプログラミング言語によって異なるとのこと（知らなかった・・・）。
- x以下の整数のうち最大のもの（$\lfloor x \rfloor$）
- 小数点以下の部分を捨てる
Pythonでは「切り捨て」は前者のロジック（x以下の整数のうち、最大のもの）を使っているとのことです。
そのため、Pythonで除算演算子を使った計算では下記のような結果となります。
print(7 // 3)
# 2 （「2.777...」以下の整数のうち最大のもの）
print(7 // -3)
# -3 （「-2.777...」以下の整数のうち最大のもの）
Pythonにおける「切り上げ除算」の求め方
今回の問題において、Pythonで単純にX/10を計算すると$\lfloor \frac{X}{10} \rfloor$が結果として得られることになり、問題で求められている$\lceil \frac{X}{10} \rceil$をどのように求めるかが鍵になります。
これを解くにあたり、考えやすくするため、まずはx/3を例として考えてみます。
- $\lfloor \frac{x}{3} \rfloor$・・・
x/3以下の整数のうち最大のもの（Pythonにおける除算結果） - $\lceil \frac{x}{3} \rceil$・・・
x/3以上の整数のうち最小のもの（今回求めたいもの）
すると、下記のような結果となります。
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| $\lfloor \frac{x}{3} \rfloor$ | 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 |
| $\lceil \frac{x}{3} \rceil$ | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 4 |
上記の結果を眺めると、今回求めたい$\lceil \frac{X}{3} \rceil$は$\lfloor \frac{X}{3} \rfloor$のXを右に2個（3-1）シフトした計算結果と同じになることがわかるかと思います。
つまり、下記の計算式で$\lceil \frac{a}{3} \rceil$を求めることができることがわかります。
$\lceil \frac{x}{3} \rceil = \lfloor \frac{a+3-1}{3} \rfloor$
| a | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| $\lfloor \frac{a}{3} \rfloor$ | 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 |
| $\lceil \frac{a}{3} \rceil$ | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 4 |
| $\lfloor \frac{a+2}{3} \rfloor$ | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 4 |
よって、Pythonにおける「切り上げ除算」の求め方は、以下の計算式によって導けるため、
$\lceil \frac{a}{b} \rceil = \lfloor \frac{a+b-1}{b} \rfloor$
2024/04/27 追記
上記はbが正の場合のみ成り立ちます。
@fujitanozomu さん
ご指摘ありがとうございます。
今回の問題は、下記のように実装することで解くことができます。
N = int(input())
ans = (N+9)//10
print(ans)
以上です。