B - Integer Division Returns Editorial
by
Nyaan
初めに切り上げ除算の説明、およびそのやり方について説明します。
整数 \(a\) と \(b\) が与えられたときに、\(a \div b\) の小数点以下を切り上げた整数を求めることを 切り上げ除算 と言います。
- 例えば \(a = 7, b = 3\) の時は、\(7 \div 3 = 2.3333\dots\) で小数部を切り上げることで \(3\) を得ることが出来ます。
一方、プログラミング言語で使用される /
(除算演算子, Python では //
) は、基本的には切り捨て除算、すなわち小数点以下を切り捨てる除算を行います。(これは厳密には \(a, b\) が正の時の話です。詳細は後述) そこで、/
を利用して切り上げ除算を計算するためには少し工夫が必要です。
簡単のため、はじめに \(a \geq 0, b \gt 0\) の場合を説明します。また、
- \(\lceil x \rceil\) を「\(x\) 以上の整数のうち最小のもの」
- \(\lfloor x \rfloor\) を「\(x\) 以下の整数のうち最大のもの」
とします。
\(x\) が正の時、\(\left \lceil x \right \rceil\) は \(x\) の小数点以下を切り上げる操作と、\(\left \lfloor x \right \rfloor\) は \(x\) の小数点以下を切り捨てる操作と一致します。(負の時は一致しません。詳細は後述) また、次の等式が成り立つことが確認できます。(証明は省略します)
\[\left \lceil \frac{a}{b} \right \rceil = \left \lfloor \frac{a + b - 1}{b} \right \rfloor\]
よって、この等式を利用して、
(a + b - 1) / b
のように 「\(a\) に \(b-1\) を足して、その後に切り捨て除算を行う」問う操作を実装することで、\(a \div b\) の切り上げ除算を計算できます。この (a + b - 1) / b
という式は非常によく使う式なので、知らなかった人は是非覚えておきましょう。
\(a\) が正の場合は上式を使えば問題は解決するのですが、今回の出題では \(a\) は負の値を取る可能性があり、これが大きな問題となっています。なぜならば、負数の切り捨て除算は \(2\) 通りの方法があるからです。
「\(x\) の小数点以下を切り捨てる」という操作は、次の 2 通りの方法で解釈することが出来ます。
- \(\lfloor x \rfloor\) を計算する
- 小数点以下の部分を捨てる
\(x\) が正の場合はどちらの解釈でも同じ答えが得られます。例えば \(3.7\) という数の小数点以下を切り捨てる時は、
- \(\lfloor 3.7 \rfloor = 3\) なので \(3\) とする
- \(3.7\) の \(.7\) を捨てて \(3\) とする
となり同じ値が得られます。一方、\(x\) が負の時、例えば \(-2.4\) という数の小数点以下を切り捨てる時は
- \(\lfloor -2.4 \rfloor = -3\) なので \(-3\) とする
- \(-2.4\) の \(.4\) の部分を切り捨てて \(-2\) とする
となり、異なる値が得られることがわかります。
今回の問題は \(\dfrac{X}{10}\) を計算する問題でした。先ほど紹介した
\[\left \lceil \frac{a}{b} \right \rceil = \left \lfloor \frac{a + b - 1}{b} \right \rfloor\]
という式は \(a, b\) の正負に関わらず成立するので、\(a = X, b = 10\) を代入すると
\[\left \lceil \frac{X}{10} \right \rceil = \left \lfloor \frac{X + 10 - 1}{10} \right \rfloor = \left \lfloor \frac{X+9}{10} \right \rfloor\]
となります。今回の問題では (X + 9) / 10
を 「1. \(\lfloor x \rfloor\) を計算する」という解釈で計算すれば答えを得ることが出来ます。
しかし、切り捨て除算における切り捨ての挙動は言語によって異なり、
- \(\lfloor x \rfloor\) を計算する \(\to\) Python などが採用
- 小数点以下の部分を捨てる \(\to\) C++ などが採用
というようになっています。よってこの問題では言語によって答えが変わるため、解説で説明されていない言語を使用している人は、自身の使っている言語がどちらの挙動を示すかを調べてみることをお勧めします。
ここでは Python と C++ における解法を示します。
Python の場合
Python は切り捨て除算の切り捨ての際に「\(\lfloor x \rfloor\) を計算する」という挙動を取ります。
よって、今回の問題では自然に実装すればこの問題を解くことが出来ます。
- 実装例
X = int(input())
print((X + 9) // 10)
ちなみに、math.ceil
関数を用いて下図のようなコードを書く人もいると思いますが、これは間違いです。(実際、入出力例 5 で正しい答えを返さないと思います。)
- 誤答例
import math
X = int(input())
print(math.ceil(X / 10))
なぜならば、\(X / 10\) を計算した時点で値が float
型になりますが、この時に計算誤差が発生するからです。
Python の float
や C++ の double
のような一般的な小数型(倍精度浮動小数点型)は高々 \(2\) 進 \(53\) 桁 (\(10\) 進数換算で約 \(16\) 桁) 程度の精度しか持ちません。よって、\(10^{18}\) のような大きい数を計算しようとすると誤差が発生して正しい計算が出来なくなります。
この問題に限らず、競技プログラミングで切り捨て/切り上げ除算をする時に float
型を経由して計算するのは、将来的にバグの原因となる危険があるのでお勧めしません。誤差の影響を避けるために、整数型のみを利用して切り捨て/切り上げ除算を計算するようにしましょう。
C++ の場合
C++ (正確には C++11 以降) における除算は「小数部分を無視した数学的な商」を計算するという旨が規格に書かれています。(参考: C++ 国際標準規格) つまり、商が \(-2.4\) だった場合は \(.4\) の部分を無視して \(-2\) を答えとして返します。これは先ほど説明した「2. 小数点以下の部分を捨てる」というパターンです。
このような整数除算では、「割られる数が負である」 + 「余りが発生している」場合に、\(\lfloor x \rfloor\) を計算したときの答えよりも \(1\) 大きい答えを返してしまいます。
よってそのようなケースでは出てくる答えから \(1\) を引くようにすることで、正しい答えを求めることができます。
- 実装例
#include <iostream>
using namespace std;
int main() {
long long X;
cin >> X;
if ((X + 9) < 0 and (X + 9) % 10 != 0) {
cout << (X + 9) / 10 - 1 << endl;
} else {
cout << (X + 9) / 10 << endl;
}
}
以上の方法により、この問題を C++, Python でともに解くことが出来ました。
なお、今回の問題よりもやや易しい類題として ABC239B: Integer Division があります。今回の問題を間違えてしまった人は復習用としてお使いください。(また、本解説は ABC239B の解説 の表現を援用している箇所があります。ご了承ください。)
posted:
last update: